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

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.当我实现类似的置换序列算法时,这导致了15%的改进.

Answer 2

计算元素的总和和平方和(对于平方和,您将需要64位值).从这些中你可以恢复哪个元素被修改:

减去未修改数组的预期值.如果x被移除并且y重复,则得到差的y - x和y ² - x ² =(y + x)(y - x)的平方和.从那以后很容易恢复x和y.

编辑:请注意,这可能比pigeonhole排序更快,因为它在阵列上线性运行,因此更加缓存友好.