找出缺失的整数

电玩女神 2022-07-16 10:52 131阅读 0赞

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

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

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

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

**此解法应该是大多数人能想到的方法，但解法虽然在时间上是最优的，但额外开辟了空间。那么怎么样能降低空间复杂度呢？**

**解法二：先把数组元素进行排序，然后遍历数组，检查任意俩个相邻元素值是否连续，如果不连续，则中间缺少的整数就是所要寻找的；如果全部连续，则缺少的整数就是1或100.**

**分析：假设数组长度是N,如果用时间复杂度为O(N\*LogN)的排序算法进行排序，那么该解法的时间复杂度是O(N\*logN)，空间复杂度是O(1).**

**OK，这种解法没有开辟额外空间但是时间复杂度又大了。那有没有办法让时间和空间都优化麽？**

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

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

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

**分析：如果继续按刚才的求和方法肯定不行，因为根本不知道每个整数出现的次数，同时又要保证时间空间最优，所以此时我们想到用异或运算（在位运算时相同位结果为0，不同为1）**

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

**分析：假设数组长度是N,那么该解法的时间复杂度是O(N)，空间复杂度是O(1).**

**题目第二次扩展：一个无序数组里有若干个正整数，范围从1-100,其中98个整数都出现了偶数次，只有俩个整数出现了奇数次（比如1,1,2,2,3,4,5,5），如何找到这个出现奇数次的整数？**

**分析：这次要找俩个赠书，刚才的方法以及不够用了。把数组所有元素异或，最终只会得到俩个整数的异或结果...于是此时我们想到分治法，如果把数组分成俩部分，每一部分包含一个奇数次整数，这样就回归到上一题的情况。**

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

**举个例子：如果最终异或结果是5，转换为二进制是00000101.此时我们可以选择任意一个是1的二进制位来分析，比如末尾是1，说明A和B转为二进制的末位不同，必定其中一个整数的末位是1，另一个整数末位是0.**

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

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

**以上分享自算法爱好者**

[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关面试中的算法（查找缺失的整数）

面试中的算法（缺失的一个整数）

╰半橙微兮°/ 2024年05月28日 10:22/ 0 赞/ 41 阅读

相关 nowcoder NC30 缺失的第一个正整数

目录题目描述：分析：完整代码： -------------------- [题目链接： ![icon-default.png?t=N7T8][icon-defa

比眉伴天荒/ 2023年10月15日 23:49/ 0 赞/ 5 阅读

相关（每日一练c++）CC172 找出缺失的整数

前言 C++是一种计算机高级程序设计语言，由C语言扩展升级而产生，最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。 C++既可以进行C语言的过程化

柔光的暖阳◎/ 2023年10月04日 18:02/ 0 赞/ 3 阅读

相关 LeetCode 1539. 第 k 个缺失的正整数 JAVA

给你一个严格升序排列的正整数数组 arr 和一个整数 k 。请你找到这个数组里第 k 个缺失的正整数。示例 1：输入：arr = [2

怼烎@/ 2022年12月07日 01:24/ 0 赞/ 96 阅读

相关 Java中找出缺失的数字

![复制代码][48304ba5e6f9fe08f3fa1abda7d326ab.png] 给定一组连续的整数，例如：10，11，12，……，20，但其中缺失一个数字

朴灿烈づ我的快乐病毒、/ 2022年10月09日 12:19/ 0 赞/ 205 阅读

相关 1539. 第 k 个缺失的正整数

[https://leetcode-cn.com/problems/kth-missing-positive-number/][https_leetcode-cn.com_pr

墨蓝/ 2022年09月05日 01:57/ 0 赞/ 118 阅读

相关找出缺失的整数

一个无序数组里有99个不重复的正整数，范围从1-100，唯独缺少一个赠书，如何找出这个缺失的整数？解法一：创建一个HashMap，以1-100为键，值都是0，然后遍历整

电玩女神/ 2022年07月16日 10:52/ 0 赞/ 132 阅读

相关算法-找出缺失的整数

题目：一个无序数组里有99个不重复正整数，范围从1到100，唯独缺少一个整数。如何找出这个缺失的整数？解法一：创建一个HashMap，以1到100为键，值都是0 。然后

深碍√TFBOYSˉ_/ 2022年07月15日 07:58/ 0 赞/ 113 阅读

相关【Python】第一个缺失的整数

第一个缺失的整数 > 给定一个数组A\[0…N-1\]，找到从1开始，第一个不在数组中的正整数。 > 如3,5,1,2,-3,7,14,8输出4 循环不变式

超、凢脫俗/ 2022年05月22日 08:25/ 0 赞/ 135 阅读

相关找出重复的整数

在一个给定的数型组中，找出重复的整数: 比如int array\[5\] = \{1,1,3,3,4,5,6\}重复的整数是1 ，3。我的想法，先对数组进行排序，使数组处

谁借莪１个温暖的怀抱￠/ 2022年05月19日 11:40/ 0 赞/ 196 阅读