漫画算法：找出缺失的整数

正文

请到「今天看啥」查看全文

由于数组中缺少一个整数，最终一定有99个键对应的值等于1, 剩下一个键对应的值等于0。遍历修改后的HashMap，找到这个值为0的键。

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

解法二：

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

假设数组长度是N，如果用时间复杂度为O（N*LogN）的排序算法进行排序，那么该解法的时间复杂度是O（N*LogN），空间复杂度是O（1）。

解法三：

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

请到「今天看啥」查看全文