理解在数组中查找重复项的概念

Question

我找到了一种方法来查找一个元素范围从0到n-1的n个元素的重复项。

Traverse the array. Do following for every index i of A[].
{
    check for sign of A[abs(A[i])] ;
    if positive then        
      make it negative by   A[abs(A[i])] = -A[abs(A[i])];
    else  // i.e., A[abs(A[i])] is negative
      this element (ith element of list) is a repetition
}

这个方法可以正常工作，但我不明白它是如何工作的。有人能解释一下吗？

我基本上是在寻找这个算法的证明或更简单的理解！

- poorvank

---

尝试手动在大小为3的数组上执行此操作，并增加其大小。 - mmmmmm

@Mark：我已经尝试过并且它工作得很好。我只是在寻找一种更简单的解释/证明，以便更清楚地理解！ - poorvank

Answer 1

使用每个数组元素的符号位作为一个一位标记数组来指示元素的存在或不存在，这实际上是在作弊。这可能比使用单独的位集合数组更快，但它肯定利用了你正在使用无符号值的有符号表示（int），因此你有一个多余的未使用位可以使用。如果您的值是带符号的，则这将不起作用。

- Lee Daniel Crocker

Answer 2

算法在数组中的每个数字的符号中存储额外的信息。 A[i] 中的符号表示在处理过程中是否先前发生过 i：如果它是负数，则发生了一次。

注意：“元素从0到n-1。” - 哦，好吧，您不能在 0 中存储符号，因此这不是该任务的正确算法。

- Karoly Horvath

---

然而，您可以将-（INT_MAX + 1）解释为-0，但这需要一些特殊处理，最好还是使用单独的位集。 - Lee Daniel Crocker

Answer 3

请查看http://www.geeksforgeeks.org/find-the-two-repeating-elements-in-a-given-array/的第五种方法。

那里的示例可能会对您有所帮助。

- sara