点击关注公众号，Java干货及时送达
今天，我们来看看腾讯终面的两道算法题目，看似简单，但要现场全部做对，也不容易，直接决定了能否拿到腾讯offer, 一起来看看吧。有n个QQ号码，除1个孤单的QQ号码外，其余的QQ号码都是成双成对的，求这个孤单的QQ号码，要求：时间复杂度为O(n), 空间复杂度为O(1).如果你不懂这个题目的具体意思，那我来画个动图，相信你就会明白了。看动图：两个520是一对的，两个216也是一对的，而剩下的111是孤单的。那么，怎么求出111这个孤单的QQ号码呢？且听我慢慢道来。
方法1: 直接记录
先来介绍最直接的方法：遍历每个元素，记录每个号码出现的次数，比如：hash_map[520] = 2hash_map[216] = 2hash_map[111] = 1
于是乎，可以轻易地看到111出现的次数是1，所以，孤单的QQ号就是111.然而，这种方法无法通过腾讯的面试，因为空间复杂度太大，不符合要求。方法2: 排序求解
于是，想到了计算机中最常用的方法：排序法。显而易见，排序后结果为：
显然，排序后就更清楚了，再遍历一遍，就容易知道孤单的QQ号是111.
一提到排序算法，很显然知道，时空复杂度不达标，无法通过腾讯的面试。方法3: 异或求解
遇到这种题目，需要有一定的敏感度，其实就是需要刷题。直接异或搞起：result = 520 ^ 216 ^ 216 ^ 520 ^ 111 = (520 ^ 520) ^ (216 ^ 216) ^ 111 = 0 ^ 0 ^ 111 = 111
根据异或算法的交换律和结合律，很容易破解。方法挺巧妙的，也挺实用。显然，时空复杂度符合要求，可以通过腾讯的面试。第一题万事大吉了哦。关于异或，我们需要知道，相同两数的异或值为0，而0和x的异或值仍为x.接下来，我们用实际的程序验证一下，有兴趣的朋友也可以亲自动手试下：#include 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).如果你不懂这个具体题目，那我来画个动图，相信你就会明白。看动图：两个520是一对的，两个216也是一对的，剩下的734和111是孤单的。那么，怎么求出734和111这两个QQ号码呢？我相信，你肯定已经放弃了计数法和排序法，这就对了。异或算法搞起来！1. 探索异或
result = 520 ^ 216 ^ 734 ^ 216 ^ 520 ^ 111 = (520 ^ 520) ^ (216 ^ 216) ^ 734 ^ 111 = 0 ^ 0 ^ 734 ^ 111 = 734 ^ 111 = 689
糟糕了，貌似这次用异或算法不灵了。因为题目变难了，题目中有2个孤单数，上述的689并不是正解。迷茫之际，必须探索新的思路，才有新的出路。我们先来看看二进制异或值的计算方法，如下表格所示：那么，我们来看看734和111的异或过程，其中，a为734，b为111，直接用二进制异或，如下表格所示：可以看到，a和b的异或二进制值是：0000 0010 1011 0001，也就是十进制的689，所以result = 689.由于734和111不同，故异或值不可能是0，因此，对于它们异或值689的二进制值而言，必然存在一个1.可以看到，689的最后一位是1，因此可知：734和111的二进制的最后一位，必然是一个为0，另一个为1.2. 探索分组
接着，我们可以根据二进制中最后一位是否为1，把原来的数据分为两类。先来看看原来数据的二进制值吧：
很显然，通过上述规则的划分，我们把原来的数据分成了两组，分别是上面表格中的红色部分和蓝色部分。接下来，分别对这两组求异或，就可以得到两个最后的值，也就是我们苦苦追求的两个孤单数，具体如下。result1 = 520 ^ 216 ^ 734 ^ 216 ^ 520 = (520 ^ 520) ^ (216 ^ 216) ^ 734 = 734
3. 步骤总结
Step1: 计算出原数组的所有数字的异或值result, result的值必然不为0，且一定是两个孤单数的异或值。
Step2: result的二进制中，必然存在第k位的值为1. 以第k位是否为1来作为判断标准，对原数组进行划分。
Step3: 将原数组二进制第k位为0的数，认为是第一个集合，并计算出它们的异或值，形成第一个孤单数。
Step4: 将原数组二进制第k位为1的数，认为是第二个集合，并计算出它们的异或值，形成第二个孤单数。
该算法非常巧妙，时间复杂度为O(n), 空间复杂度为O(1), 完全符合题目的要求，可以通过腾讯的面试。
异或算法很巧妙，在面试中也会经常用到，需要引起重视。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。
