在整数数组中查找第一个非重复数

Question

我得到了这个问题的考试:

给定整数数组,使用O(N)时间复杂度和O(1)空间复杂度找到第一个不在数组中重复的数字.

我想不出任何解决方案.我知道我可以迭代数组并维护一个linkedhashmap,它将存储数组元素和它出现的次数,然后最后我必须搜索hashmap来找到那个数字.空间复杂度大于O(1)但我想不出其他解决方案.

我也仔细阅读问题,并说数组的最大尺寸为100万.我认为如果我们可以创建一个自定义散列图,它将使用100万大小的固定大小的数组,那么这可以在O(1)空间复杂度中实现,因为在这种情况下,所需的存储将是恒定的,但如果我是正确的则不确定.如果有任何其他解决方案,请告诉我.

Answer 1

如果除一个元素之外的所有元素恰好有两个（或 2 的倍数）条目，该元素将不重复，则可以使用 XOR 运算符。

例子：

int x=arr[0];
for(i=1;i<1000;i++)
  x^=a[i];
printf("Non-repeating: %d",x);

任何数字与其自身异或都是 0。因此，如果任何数字出现两次，则整个异或结果将为 0，从而在 中仅留下不重复的数字x。

注意：如果您有 100 万个数字，则用于存储 XOR 结果的变量必须足够大。