c - 如何以最小的复杂性识别数组中的重复数字？

Question

有一个大小为 10,000 的数组。它以随机顺序存储数字 1 到 10,000。
每个数字只出现一次。

现在，如果从该数组中删除任何数字并将任何其他数字复制到数组中。

我们如何以最小的复杂性识别重复的数字？

注意:我们不能使用另一个数组。

Answer 1

最快的方法是 O(N) 就地鸽巢排序。

从数组的第一个位置 a[0] 开始。假设它的值为 5。您知道 5 属于 a[4]，因此交换位置 0 和 4。现在 a[0] 中有一个新值。将其交换到需要去的地方。

重复直到 a[0] == 1，然后继续 a[1] 并交换直到 a[1] == 2等

如果在任何时候你最终试图交换两个相同的值，那么你就找到了重复项!

运行时间:O(N)，系数很低，提前退出。所需存储空间:零。

奖励优化:计算发生了多少次交换，如果 n_swaps == array_size 则提前退出。当我实现 a similar algorithm 时，这导致了 15% 的改进用于排列序列。