原文：How to find a unique number in a list containing pairs? – Yonatan Kra

翻译：码中人

在数组中找到唯一的数字，听起来很简单吧！

一句话描述可能会产生误导，那我们就从一个具体的数组开始：

[1,3,17,3,1]

以上给出的数组，唯一出现一次的数字是17，其余的数字1，3都出现过两次。接下来，我们就以这个数组为用例来测试解决办法。

有3种主要的方法可以找到这个唯一数。从性能上看，可能会是：

• 时间复杂度O(n*n)
• 时间复杂度O(n)和空间复杂度O(n)
• 时间复杂度O(n)和空间复杂度O(1)空间

读完这篇文章后，你会知道这三种方法。

1 天真无邪法

让我们找出[1,3,17,3,1]中的唯一数字。很简单。

这个方案会检查所有的数字，并验证它们是不是重复的。最坏的情况是，我们对列表中的每个成员都进行一次检查。这意味着，时间复杂度为O(n*n)。

2 线性阶方法

在解决这类问题，我们通常希望以线性方式解决。方法是用对象字面量来记住哪些数字出现了不止一次。

我们创建一个叫memo对象，来存储出现数字的次数。然后我们在nums数组上进行迭代。如果这个数字是第一次出现，创建一个与数字同名属性，标记为1。如果再次遇到这个数字，就加1。

然后再遍历memo对象的属性，找到只出现1次的数。

这段代码没有嵌套循环，时间复杂度是线性的O(n)。但是我们创建了一个对象，它占用的内存为O(n/2)空间（实际上是O(n)）。我们怎么样才能进一步优化呢？

3 按位异或（Bitwise XOR）

按位异或有两个步骤：

1. 将运算数变成一个有符号的32位二进制数。
2. 返回一个新的数字，规则如下：如果两个比特都是1或0，返回0。否则–返回1。

下面是一个例子。4 ^ 5

4在二进制中是100，而5是101。把它们变成32位，只是在左边垫上零。

最终，我们将需要对这两个二进制数字(100和101）进行异或，

1 and 1 => 0

0 and 0 => 0

0 and 1 => 1

结果是001，也就是1。而相同的数字相异或，如4^4，结果为0。

如果我们有一个包含成对数的数组，做下面的操作，结果是0。

[1,2,3,4,5,6,7,1000000,1,2,3,4,5,6,7,1000000].reduce((val, num) => val ^ num)

注意，是成对的数。

如果在以上数组中添加一个唯一的数，会怎么样？

[1,2,3,4,5,6,7,1000000,8,1,2,3,4,5,6,7,1000000].reduce((val, num) => val ^ num)

在按位异或时，相同的数字会抵销，有一个独特的值会 “脱颖而出”。同时，按位运算不用考虑元素的顺序。

现在我们有了一个线性方案，并且空间复杂度为O(1)。

总结

在一个包含成对相同数字的数组中寻找一个唯一的值是一个小问题。这个问题本身并不十分有趣，也没有具体的应用场景，可能只在面试时被问到。

在这篇文章中，我们使用了两种在线性时间内解决它的方法。希望你能借此了解按位异或这个小技巧。

:)。