zhao-chu-que-shi-de-zheng-shu.md

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

法1：

• 创建一个HashMap，以1到100为键，值都是0 。然后遍历整个数组，每读到一个整数，就找到HashMap当中对应的键，让其值加一。由于数组中缺少一个整数，最终一定有99个键值等于1, 剩下一个键值等于0。遍历修改后的HashMap，找到这个值为0的键。假设数组长度是N，那么该解法的时间复杂度是O（1），空间复杂度是O（N）

法2：

• 先把数组元素进行排序，然后遍历数组，要么有其中两个相邻元素之间的差不是1，要么缺失的整数是1或100。假设数组长度是N，如果用时间复杂度为O（NLogN）的排序算法进行排序，那么该解法的时间复杂度是O（NLogN），空间复杂度是O（1）。

法3：

• 很简单也很高效的方法，先算出1+2+3....+100的合，然后依次减去数组里的元素，最后得到的差，就是唯一缺失的整数。假设数组长度是N，那么该解法的时间复杂度是O（N），空间复杂度是O（1）

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

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

---

原文链接: 找出缺失的整数