5.12.1 “五行”缺一个整数
下面考你一道算法题：在一个无序数组里有99个不重复的正整数，范围从1到100……
题目
在一个无序数组里有99个不重复的正整数，范围是1～100，唯独缺少1个1～100中的整数。如何找出这个缺失的整数？
哦，让我想想……
有了！创建一个哈希表，以1到100这100个整数为Key，然后遍历数组。
解法1：
创建一个哈希表，以1到100这100个整数为Key。然后遍历整个数组，每读到一个整数，就定位到哈希表中对应的Key，然后删除这个Key。
由于数组中缺少1个整数，哈希表最终一定会有99个Key被删除，从而剩下1个唯一的Key。这个剩下的Key就是那个缺失的整数。
假设数组长度是n，那么该解法的时间复杂度是O(n)，空间复杂度是O(n)。
OK，这个解法在时间上是最优的，但额外开辟了内存空间。那么，有没有办法降低空间复杂度呢？
哦，让我想想……
有了！首先给原数组排序，然后……
解法2：
先把数组元素从小到大进行排序，然后遍历已经有序的数组，如果发现某两个相邻元素并不连续，说明缺少的就是这两个元素之间的整数。
假设数组长度是n，如果用时间复杂度为O(nlogn)的排序算法进行排序，那么该解法的时间复杂度是O(nlogn)，空间复杂度是O(1)。
OK，这个解法没有开辟额外的空间，但是时间复杂度又太大了。有没有办法对时间复杂度和空间复杂度都进行优化呢？
哦，让我想想……
有了！先算出1～100的累加和，然后再依次减去数组里的所有元素，最后的差值就是所缺少的整数。这么简单的办法我竟然才想到！
解法3：
这是一个很简单也很高效的方法，先算出1+2+3+…+100的和，然后依次减去数组里的元素，最后得到的差值，就是那个缺失的整数。
假设数组长度是n，那么该解法的时间复杂度是O(n)，空间复杂度是O(1)。
OK，对于没有重复元素的数组，这个解法在时间和空间上已经最优了。但如果把问题扩展一下……
5.12.2 问题扩展
题目第1次扩展：
一个无序数组里有若干个正整数，范围是1～100，其中99个整数都出现了偶数次 ，只有1个整数出现了奇数次 ，如何找到这个出现奇数次的整数？
哦，让我想想……
按照刚才的方法先求和肯定不行，因为根本不知道每个整数出现的次数……同时又要保证时间和空间复杂度的最优，怎么办呢？
让我提示你一下吧，你知道异或运算 吗？
异或运算，我当然知道，在进行位运算时，相同位得0，不同位得1。可是怎么应用到这个题目上面呢？
啊，我想到了！只要把数组里所有元素依次进行异或运算，最后得到的就是那个缺失的整数！
解法：
遍历整个数组，依次做异或运算。由于异或运算在进行位运算时，相同为0，不同为1，因此所有出现偶数次的整数都会相互抵消变成0，只有唯一出现奇数次的整数会被留下。
让我们举一个例子：给出一个无序数组{3,1,3,2,4,1,4}。
异或运算像加法运算一样，满足交换律和结合律，所以这个数组元素的异或运算的结果如下图所示。
假设数组长度是n，那么该解法的时间复杂度是O(n)，空间复杂度是O(1)。
这个方案已经非常好了。我们把问题最后扩展一下，如果数组里有2个整数出现了奇数次 ，其他整数出现偶数次，该如何找出这2个整数呢？
题目第2次扩展：
假设一个无序数组里有若干个正整数，范围是1～100，其中有98个整数出现了偶数次，只有2个 整数出现了奇数次，如何找到这2个出现奇数次的整数？
啊，这次要找2个整数，刚才的方法已经不够用了。因为把数组所有元素进行异或运算，最终只会得到2个整数的异或运算结果。
我来提示你一下吧，你知道分治法吗？
说起分治法，我似乎想到了什么……如果把数组分成两部分，保证每一部分都包含1个出现奇数次的整数，这样就与上一题的情况一样了。
终于想到了！首先把数组元素依次进行异或运算，得到的结果是2个出现了奇数次的整数的异或运算结果，在这个结果中至少有1个二进制位是1。
解法：
把2个出现了奇数次的整数命名为A和B。遍历整个数组，然后依次做异或运算，进行异或运算的最终结果，等同于A和B进行异或运算的结果。在这个结果中，至少会有一个二进制位是1（如果都是0，说明A和B相等，和题目不相符）。
举个例子，给出一个无序数组{4,1,2,2,5,1,4,3}，所有元素进行异或运算的结果是00000110B。
选定该结果中值为1的某一位数字，如00000110B的倒数第2位是1，这说明A和B对应的二进制的倒数第2位是不同的。其中必定有一个整数的倒数第2位是0，另一个整数的倒数第2位是1。
根据这个结论，可以把原数组按照二进制的倒数第2位的不同，分成两部分，一部分的倒数第2位是0，另一部分的倒数第2位是1。由于A和B的倒数第2位不同，所以A被分配到其中一部分，B被分配到另一部分，绝不会出现A和B在同一部分，另一部分既没有A，也没有B的情况。
这样一来就简单多了，我们的问题又回归到了上一题的情况，按照原先的异或算法，从每一部分中找出唯一的奇数次整数即可。
假设数组长度是n，那么该解法的时间复杂度是O(n)。把数组分成两部分，并不需要借助额外的存储空间，完全可以在按二进制位分组的同时来做异或运算，所以空间复杂度仍然是O(1)。
没错，就是这个思路。请你按照这个思路来写一下代码。
好的，我来试试！
1. public static int[] findLostNum(int[] array) {
2. //用于存储2个出现奇数次的整数
3. int result[] = new int[2];
4. //第1次进行整体异或运算
5. int xorResult = 0;
6. for(int i=0;i
7. xorResult^=array[i];
8. }
9. //如果进行异或运算的结果为0，则说明输入的数组不符合题目要求
10. if(xorResult == 0){
11. return null;
12. }
13. //确定2个整数的不同位，以此来做分组
14. int separator = 1;
15. while (0==(xorResult&separator)){
16. separator<<=1;
17. }
18. //第2次分组进行异或运算
19. for(int i=0;i
20. if(0==(array[i]&separator)){
21. result[0]^=array[i];
22. }else {
23. result[1]^=array[i];
24. }
25. }
26.
27. return result;
28. }
29.
30. public static void main(String[] args) {
31. int[] array = {4,1,2,2,5,1,4,3};
32. int[] result = findLostNum(array);
33. System.out.println(result[0] + "," + result[1]);
34. }
很好，我们的技术面试就到这里。请你稍等一下，我去叫HR来和你谈谈。10min后……
就这样，小灰拿到了职业生涯中的第一个offer，但这并不意味着结束，小灰的程序员之路才刚刚开始。