如何降低给定代码的时间复杂度?

Question

检查代码检查重复元素，如果有重复元素返回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;
}

我认为这是正确的代码，但它显示了一个时间限制超过错误。

Answer 1

降低给定代码的时间复杂度?

OP的方法是O(n*n)

下面是一个O(n*log n)的方法

1. 复制数组a到新数组b

2. 用qsort()排序b

3. 遍历b查找相邻重复。

Answer 2

如果你有足够的内存…

假设4个字节的int(这是常见的)，您可以通过使用半千兆字节的动态内存在O(N)内完成。它是通过创建一个unsigned char数组并让每个位代表一个int值来完成的。

类似:

#include <stdio.h>
#include <stdlib.h>
int containsDuplicate(int *a, int n)
{
int res = 0;
size_t sz = (1ULL << 32) / 8;  // or just (1ULL << (32-3))
unsigned char* p = calloc(sz, 1);
if (!p) exit(1);
for (size_t i = 0; i < n; ++i)
{
unsigned int u = a[i];
unsigned int idx = u / 8;
unsigned int bit = u % 8;
unsigned char v = p[idx];
if (((v >> bit) & 0x1) != 0)
{
res = 1;
break;
}
p[idx] |= (1 << bit);
}
free(p);
return res;
}

int main()
{
int arr[] = {435435, 7657, 43243, 435435, 989723};
size_t sz_a = sizeof arr / sizeof arr[0];
if (containsDuplicate(arr, sz_a))
{
puts("Duplicate found");
}
else
{
puts("No duplicate found");
}
arr[3] = 42;
if (containsDuplicate(arr, sz_a))
{
puts("Duplicate found");
}
else
{
puts("No duplicate found");
}
return 0;
}

输出:

Duplicate found
No duplicate found