以最佳时间复杂度在未排序数组中查找重复项

Question

我知道有类似的问题，但不是那么具体

输入：n 元素数组，其未排序的 emelents 的值从 1 到 (n-1)。其中一个值重复（例如，n=5，tab[n] = {3,4,2,4,1}。

任务：找到具有最佳复杂性的重复项。

我写了算法：

int tab[] = { 1,6,7,8,9,4,2,2,3,5 };
int arrSize = sizeof(tab)/sizeof(tab[0]);

for (int i = 0; i < arrSize; i++) {
    tab[tab[i] % arrSize] = tab[tab[i] % arrSize] + arrSize;
}

for (int i = 0; i < arrSize; i++) {
    if (tab[i] >= arrSize * 2) {
        std::cout << i;
        break;
    }

但我不认为它具有最好的复杂性。你知道更好的方法/算法吗？我可以使用任何 C++ 库，但我不知道。

是否有可能获得比 O(n) 更好的复杂度？

Answer 1

就大 O 表示法而言，您无法击败 O(n)（与此处的解决方案相同）。但是，通过使用元素之和1,...,n-1众所周知的属性，您可以拥有更好的常数和更简单的算法。

int sum = 0;
for (int x : tab) {
  sum += x;
}

duplicate = sum - ((n*(n-1)/2))

这里的常量会明显更好 - 因为每个数组索引都被访问一次，这对现代体系结构来说更加缓存友好和高效。

sum（请注意，此解决方案确实忽略了整数溢出，但通过使用比数组元素多 2 倍的位，很容易解决该问题）。

Answer 2

由于要求而添加经典答案。它基于这样的想法：如果对一个数字与其自身进行异或，则会得到 0。因此，如果对从 1 到 n - 1 的所有数字以及数组中的所有数字进行异或，最终会得到重复的数字。

int duplicate = arr[0];
for (int i = 1; i < arr.length; i++) {
    duplicate = duplicate ^ arr[i] ^ i;
}