转载

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

file
file
file
file

小灰一边回忆一边讲述起当时面试的情景......

file
file
file

题目

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

file
file

解法一

创建一个HashMap,以1到100为键,值都是0 。然后遍历整个数组,每读到一个整数,就找到HashMap当中对应的键,让其值加一。

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

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

file
file
file

解法二

先把数组元素进行排序,然后遍历数组,要么有其中两个相邻元素之间的差不是1,要么缺失的整数是1或100。

假设数组长度是N,如果用时间复杂度为O(NLogN)的排序算法进行排序,那么该解法的时间复杂度是O(NLogN),空间复杂度是O(1)。

file
file
file

解法三

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

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

file

题目扩展

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

file
file
file
file

解法

遍历整个数组,依次做异或运算。由于异或在位运算时相同为0,不同为1,因此所有出现偶数次的整数都会相互抵消变成0,只有唯一出现奇数次的整数会被留下。

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

file

题目第二次扩展

一个无序数组里有若干个正整数,范围从1到100,其中98个整数都出现了偶数次,只有两个整数出现了奇数次(比如1,1,2,2,3,4,5,5),如何找到这个出现奇数次的整数?

file
file
file
file

解法

遍历整个数组,依次做异或运算。由于数组存在两个出现奇数次的整数,所以最终异或的结果,等同于这两个整数的异或结果。这个结果中,至少会有一个二进制位是1(如果都是0,说明两个数相等,和题目不符)。

举个例子,如果最终异或的结果是5,转换成二进制是00000101。此时我们可以选择任意一个是1的二进制位来分析,比如末位。把两个奇数次出现的整数命名为A和B,如果末位是1,说明A和B转为二进制的末位不同,必定其中一个整数的末位是1,另一个整数的末位是0。

根据这个结论,我们可以把原数组按照二进制的末位不同,分成两部分,一部分的末位是1,一部分的末位是0。由于A和B的末位不同,所以A在其中一部分,B在其中一部分,绝不会出现A和B在同一部分,另一部分没有的情况。

这样一来就简单了,我们的问题又回归到了上一题的情况,按照原先的异或解法,从每一部分中找出唯一的奇数次整数即可。

假设数组长度是N,那么该解法的时间复杂度是O(N)。把数组分成两部分,并不需要借助额外存储空间,完全可以在按二进制位分组的同时来做异或运算,所以空间复杂度仍然是O(1)。

file

十分钟后......

file

以上就是小灰面试的情况......

file
file
file
file

文章转载自公众号:程序员小灰

正文到此结束
本文目录