腾讯终面：孤单的QQ号码怎么找？
The following article is from 爱码有道 Author 点击关注👉👉
今天，我们来看看腾讯终面的两道算法题目，看似简单，但要现场全部做对，也不容易，直接决定了能否拿到腾讯offer, 一起来看看吧。
有n个QQ号码，除1个孤单的QQ号码外，其余的QQ号码都是成双成对的，求这个孤单的QQ号码，要求：时间复杂度为O(n), 空间复杂度为O(1).
如果你不懂这个题目的具体意思，那我来画个动图，相信你就会明白了。看动图：两个520是一对的，两个216也是一对的，而剩下的111是孤单的。
方法1: 直接记录
先来介绍最直接的方法：遍历每个元素，记录每个号码出现的次数，比如：
hash_map[520] = 2hash_map[216] = 2hash_map[111] = 1然而，这种方法无法通过腾讯的面试，因为空间复杂度太大，不符合要求。
方法2: 排序求解
于是，想到了计算机中最常用的方法：排序法。显而易见，排序后结果为：
方法3: 异或求解
遇到这种题目，需要有一定的敏感度，其实就是需要刷题。直接异或搞起：
result = 520 ^ 216 ^ 216 ^ 520 ^ 111 = (520 ^ 520) ^ (216 ^ 216) ^ 111 = 0 ^ 0 ^ 111 = 111显然，时空复杂度符合要求，可以通过腾讯的面试。第一题万事大吉了哦。
关于异或，我们需要知道，相同两数的异或值为0，而0和x的异或值仍为x.
接下来，我们用实际的程序验证一下，有兴趣的朋友也可以亲自动手试下：
#include <iostream>using namespace std;
int main(){ unsigned int a[] = {520, 216, 216, 520, 111}; unsigned int n = sizeof(a) / sizeof(a[0]); unsigned int result = 0; for(int i = 0; i < n; i++) { result ^= a[i]; } cout << result << endl; // 结果 111}有n个QQ号码，除2个孤单的QQ号码外，其余的QQ号码都是成双成对的，求这2个孤单的QQ号码，要求：时间复杂度为O(n), 空间复杂度为O(1).
1. 探索异或
result = 520 ^ 216 ^ 734 ^ 216 ^ 520 ^ 111 = (520 ^ 520) ^ (216 ^ 216) ^ 734 ^ 111 = 0 ^ 0 ^ 734 ^ 111 = 734 ^ 111 = 689糟糕了，貌似这次用异或算法不灵了。因为题目变难了，题目中有2个孤单数，上述的689并不是正解。
迷茫之际，必须探索新的思路，才有新的出路。我们先来看看二进制异或值的计算方法，如下表格所示：
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| 异或结果 | 0 | 1 | 1 | 0 |
| 十进制 | 二进制 | |
| a | 734 | 0000 0010 1101 1110 |
| b | 111 | 0000 0000 0110 1111 |
| 异或结果 | result | 0000 0010 1011 0001 |
可以看到，a和b的异或二进制值是：0000 0010 1011 0001，也就是十进制的689，所以result = 689.
由于734和111不同，故异或值不可能是0，因此，对于它们异或值689的二进制值而言，必然存在一个1.
可以看到，689的最后一位是1，因此可知：734和111的二进制的最后一位，必然是一个为0，另一个为1.
2. 探索分组
接着，我们可以根据二进制中最后一位是否为1，把原来的数据分为两类。先来看看原来数据的二进制值吧：
| 十进制 | 二进制 |
| 520 | 0000 0010 0000 1000 |
| 216 | 0000 0000 1101 1000 |
| 734 | 0000 0010 1101 1110 |
| 216 | 0000 0000 1101 1000 |
| 520 | 0000 0010 0000 1000 |
| 111 | 0000 0000 0110 1111 |
很显然，通过上述规则的划分，我们把原来的数据分成了两组，分别是上面表格中的红色部分和蓝色部分。
接下来，分别对这两组求异或，就可以得到两个最后的值，也就是我们苦苦追求的两个孤单数，具体如下。
第一组：
result1 = 520 ^ 216 ^ 734 ^ 216 ^ 520 = (520 ^ 520) ^ (216 ^ 216) ^ 734 = 734result2 = 111 ^ 0 = 1113. 步骤总结
接下来，我们来总结一下算法步骤：
Step1: 计算出原数组的所有数字的异或值result, result的值必然不为0，且一定是两个孤单数的异或值。
Step2: result的二进制中，必然存在第k位的值为1. 以第k位是否为1来作为判断标准，对原数组进行划分。
Step3: 将原数组二进制第k位为0的数，认为是第一个集合，并计算出它们的异或值，形成第一个孤单数。
Step4: 将原数组二进制第k位为1的数，认为是第二个集合，并计算出它们的异或值，形成第二个孤单数。
异或算法很巧妙，在面试中也会经常用到，需要引起重视。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。
推荐阅读：
面试官：谈谈 Exception 和 Error 的区别及注意事项
面试官又整新活，居然问我for循环用i++和++i哪个效率高？
每日打卡赢积分兑换书籍入口