arrays - 如何在 xor 方法的数组中查找重复项？算法复杂度 O(n)

Question

如何在数组中查找重复项。在逆问题的情况下，当您必须找到所有元素的唯一元素时，您只需对所有元素进行异或运算，结果我们就获得了一个唯一元素。例如

int a[] = {2, 2, 3, 3, 4, 5, 5, 16, 16};
int res = a[0];
for(int i = 0; i < 9; ++i)
    res ^= a[i];

例如给定一个数组

int a[] = {2, 4, 7, 8, 4, 5};

这里a duplicate是4，但是不清楚如何找到数组的重复元素。

Answer 1

您正在描述元素区别问题。

如果没有额外的空间（和散列），就O(n)无法解决元素差异性问题，因此您无法针对此问题修改“重复的异或算法”。

这个问题的解决方案是：

1. 对排序后的数组进行排序和迭代以查找欺骗（在排序后的数组中很容易）。这是O(nlogn)时候了。
2. 构建数据的直方图（基于哈希）并在完成后迭代直方图以验证直方图中是否所有元素的值都为 1 -O(n) 平均情况，O(n) 空间。

Answer 2

我们可以使用以下算法在 0(n) 时间内找到数组中的重复项。

  traverse the list for i= 0 to n-1 elements
  {
//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 3

一种解决方案是构建一个 Hashset。它如下 -

 1. Initialize an empty hashset.
 2. For each element in array,
     a. Check if it is present in the hashset.
        If yes, you found the duplicate
        If not, add it to the hashset.

这样您就可以找到数组中的所有重复项。

空间复杂度：O(n)；时间复杂度：O(n)