在一个无序数组里有99个不重复的正整数，范围是1～100，唯独缺少1个1～100中的整数。如何找出这个缺失的整数？

1. 哈希表（时间最优）
2. 排序
3. 累加（先计算出1~100的累加和，在依次减去数组中的数）

   问题扩展1

   一个无序数组里有若干个正整数，范围是1～100，其中99个整数都出现了偶数次 ，只有1个整数出现了奇数次 ，如何找到这个出现奇数次的整数？

异或运算：在进行位运算时，相同位得0，不同位得1。
遍历整个数组，依次做异或运算。由于异或运算在进行位运算时，相同为0，不同为1，因此所有出现偶数次的整数都会相互抵消变成0，只有唯一出现奇数次的整数会被留下。
假设数组长度是n ，那么该解法的时间复杂度是，空间复杂度是。

问题扩展2

假设一个无序数组里有若干个正整数，范围是1～100，其中有98个整数出现了偶数次，只有2个 整数出现了奇数次，如何找到这2个出现奇数次的整数？

把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 ，那么该解法的时间复杂度是。把数组分成两部分，并不需要借助额外的存储空间，完全可以在按二进制位分组的同时来做异或运算，所以空间复杂度仍然是。

public static int[] findLostNum(int[] array) {
    // 用于存储 2 个出现奇数次的整数
    int result[] = new int[2];
    // 第一次进行整体异或运算
    int xorResult = 0;
    for (int i = 0; i < array.length; i++) {
        xorResult ^= array[i];
    }
    // 如果进行异或运算的结果为 0，说明输入的数组不符合题目要求
    if (xorResult == 0) {
        return null;
    }
    // 确定两个整数的不同位置，以此来做分组
    int separator = 1;
    while (0 == (xorResult & separator)) {
        separator <<= 1;
    }
    // 第 2 次分组进行异或运算
    for (int i = 0; i < array.length; i++) {
        if (0 == (array[i] & separator)) {
            result[0] ^= array[i];
        } else {
            result[1] ^= array[i];
        }
    }
    return result;
}