在O（n）时间和O（1）空间中查找重复项

Question

输入：给定n个元素组成的数组，其中包含从0到n-1的元素，这些数字中的任何一个出现任何次数。

目标：在O（n）中查找这些重复数字，并且仅使用恒定的存储空间。

例如，假设n为7，数组为{1、2、3、1、3、0、6}，答案应该为1和3。我在这里检查了类似的问题，但答案使用了诸如HashSetetc之类的一些数据结构。

有没有同样有效的算法？

Answer 1

这是我想出的，不需要额外的符号位：for i := 0 to n - 1    while A[A[i]] != A[i]         swap(A[i], A[A[i]])    end whileend forfor i := 0 to n - 1    if A[i] != i then         print A[i]    end ifend for第一个循环对数组进行排列，因此，如果element x至少存在一次，则这些条目之一将位于position A[x]。请注意，乍一看它看起来可能不是O（n），但它是-尽管具有嵌套循环，但仍会O(N)及时运行。仅当存在一个i这样的时，才会发生交换A[i] != i，并且每个交换都将至少一个元素设置为A[i] == i，这样以前是不正确的。这意味着交换的总数（以及while循环体的执行总数）最多为N-1。第二环路打印的值x对其A[x]不等于x-由于第一循环保证，如果x存在至少一次阵列中，其中的一个实例将在A[x]，这意味着它打印的那些值x中不存在在数组。

Answer 2

caf出色的答案将打印出现在数组k-1次中k次的每个数字。这是有用的行为，但是这个问题可以说要求每个副本仅打印一次，并且他暗示了这样做的可能性而不会超出线性时间/恒定空间界限。这可以通过用以下伪代码替换他的第二个循环来完成：for (i = 0; i < N; ++i) {&nbsp; &nbsp; if (A[i] != i && A[A[i]] == A[i]) {&nbsp; &nbsp; &nbsp; &nbsp; print A[i];&nbsp; &nbsp; &nbsp; &nbsp; A[A[i]] = i;&nbsp; &nbsp; }}这利用了第一个循环运行之后的属性，如果任何值m出现多次，则保证其中一个出现在正确的位置，即A[m]。如果我们小心的话，我们可以使用该“主页”位置来存储有关是否已打印任何副本的信息。在caf的版本中，当我们遍历数组时，A[i] != i暗示这A[i]是重复的。在我的版本中，我依赖于一个稍有不同的不变式：这A[i] != i && A[A[i]] == A[i]意味着这A[i]是我们之前从未见过的重复项。（如果删除“我们之前从未见过的”部分，那么其余部分可以被认为是caf不变式的真相，并且保证所有重复项在原位都有一些副本。）一开始（在caf的第一个循环完成之后），下面我显示它在每个步骤之后都得到维护。当我们遍历数组时，A[i] != i测试的成功意味着A[i] 可能是以前从未见过的重复。如果我们以前从未看过它，那么我们希望A[i]的原位指向自己-这是在if条件的后半部分进行测试的结果。如果是这种情况，我们将其打印出来并更改家庭位置，使其指向该首次发现的重复项，从而创建一个两步的“循环”。要查看此操作不会改变我们的不变，假设m = A[i]一个特定的位置i满足A[i] != i && A[A[i]] == A[i]。显然，我们所做的（A[A[i]] = i）更改将m通过使if条件的后半部分条件失败来防止其他非住宅出现作为重复输出而起作用，但是i到达住宅位置是否起作用m？是的，因为现在，即使新i发现if条件的第一个一半A[i] != i为真，第二个一半也会测试它所指向的位置是否为家中位置，而发现不是。在这种情况下，我们已经不知道是否m或A[m]为重复的值，但我们知道，无论哪种方式，由于已经保证了这2个循环不会出现在caf的第一个循环的结果中，因此已经有报道。（请注意，如果m != A[m]恰好其中一个m和A[m]发生多次，而另一个根本不发生。）