3

我找到了一种在从 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
}

这种方法效果很好。但我不明白怎么做。有人可以解释一下吗？

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

4

3 回答 3

4

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

于 2013-08-25T20:40:50.847 回答
3

该算法将附加信息存储在数组中每个数字的符号中。

登录A[i]存储是否i在处理过程中以前发生过：如果为负，则发生一次。

注：“元素范围从 0 到 n-1。” - 哦，好吧，您无法存储登录0信息，因此这不是该任务的正确算法。

于 2013-08-25T20:36:32.350 回答
0

请参阅http://www.geeksforgeeks.org/find-the-two-repeating-elements-in-a-given-array/ 方法 5。

那里的例子可能会对你有所帮助。

于 2013-08-25T20:35:53.203 回答