微信号:programmer_club

介绍:程序员第一自媒体,与你探讨码农人生路上遇到的各类泛技术话题,定期为你推荐码农人生思考、感悟以及启迪!

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

2016-10-13 22:00 玻璃猫


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

题目:一个无序数组里有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(N*LogN),空间复杂度是O(1)。


解法三:

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

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

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

解法:

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

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

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


解法:

遍历整个数组,依次做异或运算。由于数组存在两个出现奇数次的整数,所以最终异或的结果,等同于这两个整数的异或结果。这个结果中,至少会有一个二进制位是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)。

十分钟后……

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


来源于:伯乐在线 - 玻璃猫 

原文链接:http://blog.jobbole.com/106521/

关注作者,获取更多内容



 
程序员之家 更多文章 程序员被打断工作会导致什么? Python入门 华为真的那么好进? 想有钱吗?来学习这几门语言吧 “种子”的故事
猜您喜欢 程序员究竟可以干多少年 通过自动布局来实现 iOS 动画 使用Google官方support-annotation利器 【比特科技/面试经验】学姐眼中的“比特”?? Shadowsocks 原理简介及安装指南