算法：找出正确的整数

题目：一个无序数组里有99个不重复正整数，范围从1到100，唯独缺少一个整数。如何找出这个缺失的整数？

解法一：
创建一个HashMap，以1到100为键，值都是0.然后遍历整个数组，每读到一个整数，就找到HashMap当中对应的键，让其加一。
由于数组中缺少一个整数，最终一定有99个键对应的值等于1，剩下一个键对应的值等于0。遍历修改后的HashMap，找到这个值为0的键。

假设数组长度是N，那么该解法的时间复杂度是O(1),控件复杂度是O(N)。

解法二：
先把数组元素进行排序，然后遍历数组，检查任意两个相邻元素数值是否连续。如果不连续，则中间缺少的的整数就是所要寻找的；如果全部连续，则缺少的整数不是1就是100.

假设数组长度是N，时间复杂度为O(N*LogN)（排序算法），空间复杂度是O(1)。

解法三：
很简单也很高效地方法，先算出1+2+3...+100的和，然后依次减去数组里的元素，最后得到的差，就是唯一缺失的整数。

假设数组长度是N，那么该解法的时间复杂度是O(N），空间复杂度为O(1)。

---

---

题目扩展：

题目：一个无序数组里有若干个正整数，范围从1到100，其中99个整数都出现了偶数次，只有一个整数出现了奇数次（比如1，2，2，3，3，4，5，5）,如何找到这个出现奇数次的整数？

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