文山网站建设兼职,手机在线销售网站 - 百度,朝阳市网站公司,网站开发计划书封面设计转载自 玻璃猫 程序员小灰 小灰一边回忆一边讲述起当时面试的情景...... 题目#xff1a;一个无序数组里有99个不重复正整数#xff0c;范围从1到100#xff0c;唯独缺少一个整数。如何找出这个缺失的整数#xff1f; 解法一#xff1a;
创建一个HashMap#xff0c;以1到…转载自 玻璃猫 程序员小灰 小灰一边回忆一边讲述起当时面试的情景...... 题目一个无序数组里有99个不重复正整数范围从1到100唯独缺少一个整数。如何找出这个缺失的整数 解法一
创建一个HashMap以1到100为键值都是0 。然后遍历整个数组每读到一个整数就找到HashMap当中对应的键让其值加一。
由于数组中缺少一个整数最终一定有99个键值等于1, 剩下一个键值等于0。遍历修改后的HashMap找到这个值为0的键。
假设数组长度是N那么该解法的时间复杂度是O1空间复杂度是ON。 解法二
先把数组元素进行排序然后遍历数组要么有其中两个相邻元素之间的差不是1要么缺失的整数是1或100。
假设数组长度是N如果用时间复杂度为ON*LogN的排序算法进行排序那么该解法的时间复杂度是ON*LogN空间复杂度是O1。 解法三
很简单也很高效的方法先算出123....100的合然后依次减去数组里的元素最后得到的差就是唯一缺失的整数。
假设数组长度是N那么该解法的时间复杂度是ON空间复杂度是O1。 题目扩展一个无序数组里有若干个正整数范围从1到100其中99个整数都出现了偶数次只有一个整数出现了奇数次比如1,1,2,2,3,3,4,5,5如何找到这个出现奇数次的整数 解法
遍历整个数组依次做异或运算。由于异或在位运算时相同为0不同为1因此所有出现偶数次的整数都会相互抵消变成0只有唯一出现奇数次的整数会被留下。
假设数组长度是N那么该解法的时间复杂度是ON空间复杂度是O1。 题目第二次扩展一个无序数组里有若干个正整数范围从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那么该解法的时间复杂度是ON。把数组分成两部分并不需要借助额外存储空间完全可以在按二进制位分组的同时来做异或运算所以空间复杂度仍然是O1。 十分钟后...... 以上就是小灰面试的情况......
