如何找到数组里面的唯一数字
原文：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]中的唯一数字。很简单。
function singleNumber(nums) { for (let i = 0; i < nums.length; i++) { let found = false; for (let j = 0; j < nums.length; j++) { if (nums[j] === nums[i] && i != j) { found = true; break; } } if (!found) return nums[i]; }};
console.log(singleNumber([1, 3, 17, 3, 1]))这个方案会检查所有的数字，并验证它们是不是重复的。最坏的情况是，我们对列表中的每个成员都进行一次检查。这意味着，时间复杂度为O(n*n)。
2 线性阶方法
在解决这类问题，我们通常希望以线性方式解决。方法是用对象字面量来记住哪些数字出现了不止一次。
function findUniqueNumber(nums) { let memo = {}; for (let i = 0; i < nums.length; i++) { const num = nums[i]; if (!memo[num]) { memo[num] = 1; } else { memo[num] += 1; } } return Object.keys(memo).reduce((unique, num) => { return memo[num] === 1 ? Number(num) : unique; }, NaN);};
console.log(findUniqueNumber([1, 3, 17, 3, 1]))我们创建一个叫memo对象，来存储出现数字的次数。然后我们在nums数组上进行迭代。如果这个数字是第一次出现，创建一个与数字同名属性，标记为1。如果再次遇到这个数字，就加1。
然后再遍历memo对象的属性，找到只出现1次的数。
这段代码没有嵌套循环，时间复杂度是线性的O(n)。但是我们创建了一个对象，它占用的内存为O(n/2)空间（实际上是O(n)）。我们怎么样才能进一步优化呢？
3 按位异或（Bitwise XOR）
按位异或有两个步骤：
将运算数变成一个有符号的32位二进制数。
返回一个新的数字，规则如下：如果两个比特都是1或0，返回0。否则–返回1。
下面是一个例子：4 ^ 5
4在二进制中是100，而5是101。把它们变成32位，只是在左边垫上零。
最终，我们将需要对这两个二进制数字(100和101）进行异或，
1 and 1 => 00 and 0 => 00 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)。
function findUniqueNumberBitwise(nums) { return nums.reduce((val, num) => val ^ num);}
console.log(findUniqueNumberBitwise([1, 3, 17, 3, 1]))总结
在一个包含成对相同数字的数组中寻找一个唯一的值是一个小问题。这个问题本身并不十分有趣，也没有具体的应用场景，可能只在面试时被问到。
在这篇文章中，我们使用了两种在线性时间内解决它的方法。希望你能借此了解按位异或这个小技巧。
:)。
往期推荐