要检查重复元素并在存在重复元素时返回true,否则返回false的代码。
bool containsDuplicate(int *a, int n) {
for (int i = 0; i < n; i++) {
int element = a[i];
for (int j = i + 1; j < n; j++) {
if (a[j] == element) {
return true;
}
}
}
return false;
}
我认为这是正确的代码,但它显示了一个超过时间限制的错误。
2条答案
按热度按时间46scxncf1#
以降低给定代码的时间复杂度?
时间复杂度O(nn)
时间复杂度O(nlog n)
1.将阵列
a
复制到新阵列b
1.将
b
与qsort()
排序1.遍历
b
查找相邻的重复。0wi1tuuw2#
如果你还记得...
假设
int
为4字节(这是常见的),你可以使用半个千兆字节的动态内存在O(N)中完成它,它是通过创建一个无符号字符数组,让每一位代表一个int
值来完成的。比如:
输出: