如何查找数组中唯一不出现两次的数字

arrays algorithm java

2022-08-31 16:30:31

以下内容摘自求职面试：

在包含整数的给定数组中，每个数字重复一次，除了一个不重复。编写一个函数，用于查找不重复的数字。

我想过使用HashSet，但它可能会使一切复杂化......

任何关于简单解决方案的想法？

答案 1

您可以定义一个初始化为 0 的整数“result”，然后通过将 XOR 逻辑应用于数组中的所有元素来执行一些按位运算。

最后，“result”将等于唯一只出现一次的元素。

result = 0
for i in array:
  result ^= i
return result

例如，如果您的数组包含元素 [3， 4， 5， 3， 4]，则算法将返回

3 ^ 4 ^ 5 ^ 3 ^ 4

但是 XOR 运算符 ^ 是关联和可交换的，因此结果也将等于：

（3 ^ 3） ^ （4 ^ 4） ^ 5

由于 i ^ i = 0 对于任何整数 i，而 i ^ 0 = i，因此您有

（3 ^ 3） ^ （4 ^ 4） ^ 5 = 0 ^ 0 ^ 5 = 5

答案 2

我以前见过这个问题。这是一个技巧。假设所有重复的数字正好出现两次，你这样做：

int result = 0;
for (int a : arr)
    result ^= a;