在具有最佳时间复杂性的未排序数组中查找重复项

Question

我知道也有类似的问题，但没有这种特异性

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

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

我写了alghoritm:

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;
}

但我不认为这是最复杂的。你知道更好的方法/alghoritm吗？我可以使用任何c++库，但我不知道。

有可能获得比O(n(更好的复杂性吗？

Answer 1

就big-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;
}

Answer 3

不要过于关注渐近复杂性。在实践中，最快的算法不一定是具有最低非对称复杂度的算法。这是因为没有考虑常数：O( huge_constant * N) == O(N) == O( tiny_constant * N)。

不能检查小于O(N)的N值。尽管您不需要完整通过阵列。一旦你发现重复，你就可以停止：

#include <iostream>
#include <vector>
int main() {
std::vector<int> vals{1,2,4,6,5,3,2};
std::vector<bool> present(vals.size());
for (const auto& e : vals) {
if (present[e]) {
std::cout << "duplicate is " << e << "n";
break;
}
present[e] = true;
}
}

在"；幸运案例"；副本在索引2处。在最坏的情况下，必须扫描整个矢量。平均而言，它又是O(N)的时间复杂度。此外，它使用O(N)额外内存，而您的则不使用额外内存。再次强调：单凭复杂性并不能告诉你哪种算法更快(尤其是对于固定的输入大小(。

无论你多么努力，你都无法击败O(N)，因为无论你以什么顺序遍历元素(记住已经找到的元素(，最好和最坏的情况总是一样的：要么重复出现在你检查的前两个元素中，要么是最后一个，平均而言，它将是O(N)。