algorithm - 了解在数组中查找重复项背后的概念

Question

我找到了一种方法，可以在 n 个元素的数组中查找重复项，元素范围从 0 到 n-1。

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
}

这个方法很好用。但我不明白如何。谁能解释一下？

我基本上是在寻找证明或对该算法有更简单的理解!

Answer 1

您基本上是在作弊，将每个数组元素的符号位用作指示元素存在或不存在的一位标志数组。这可能会也可能不会比简单地使用单独的位集数组更快，但它肯定会利用您使用无符号值的有符号表示 (int) 的特殊情况，因此您可以使用额外的未使用位在各个。例如，如果您的值已签名，这将不起作用。