小编her*_*ero的帖子

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

输入：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) 更好的复杂度？