算法解题：缺失的最小正整数
描述问题
问题：给定一个任意无序的整数数组 ，请返回一个在数组中没有出现的最小正整数。
限制：时间复杂度为 ，空间复杂度为 。
示例 1：
输入：nums = [3, 1, 2, 4]
输出：5
描述：1、2、3、4都在数组中，因此5是没有出现在数组中的最小正整数。
示例 2：
输入：nums = [-3, 1, 0, 4]
输出：2
描述：略
示例 3：
输入：nums = [6, 8, 7, 8]
输出：1
描述：略
请没做过此题的读者先思考片刻......
分析问题
第一步：有序数组
如果要求返回数组中存在的最小正整数，则很容易。仅遍历一次，并用一个变量记住当前的最小正整数即可。但是题目的要求是返回数组中缺失的最小正整数，这样我们必须处理无序数组，使其按照某种方式有序才行。如果数组有序，则仅需要最多一次遍历数组（ 次比较）就能完成任务。
说到数组有序，首先会想到排序算法。处理一般排序的最高效算法就要属快速排序和归并排序了。但很遗憾，它们的平均时间复杂度都是 （超出题目的限制）。
还有更高效的排序算法么？当然有啦，正是用于整数的计数排序算法。其时间复杂度正为 。但是，计数排序的空间复杂度要视数组元素（整数）取值范围而定，而整数的范围区间已经达到了几十亿。这很显然不能满足空间复杂度 的限制。
第二步：核心问题
继续思考我们会发现一个重要的问题，也是该题目的核心所在，即缺失最小正整数 的取值范围是 。
如果数组为
[1, 2, 3,..., n-1, n]，则 ，此时值最大。否则，。
这一步是解决整个问题的最关键所在，也就是说我们可以将数组 中的大小在 范围的元素在长度为 的数组中进行有序排列。而数组 的长度刚好为 ，因此我们就可以不必申请额外空间，仅在原数组上对这些元素进行排序了。
这个排序与计数排序很类似，只不过不需要在对应的位置上记录相同元素的个数。只需将数组中每个 放到 位置上。我们称每个满足 的元素为配位元素。
第三步：实现细节
遍历数组 。
当遍历到某个索引 时，可能会有下述 3 种情况：
该元素无法在数组中配位， 或者 。此时无需做任何额外处理，只进行
i++。与该元素值相同的某个元素已是配位元素， 。此时可能会有下述两种情况（无论哪种情况，同样只需进行
i++）：该元素本身就是配位元素，。
该元素本身是非配位元素，。
除了上述的其他情况：
需要交换配位 此时交换 和 的值，其目的是用当前 的值给 配位。
继续处理新的 元素 然后，（在 值保持不变的情况下）继续根据上述 3 种情况处理新的 元素。
直到遍历结束。对数组 元素的配位已处理完毕。
我们再次从头开始遍历数组 。如果到遇到一个不配位的元素（nums[i] != i+1），则缺失最小正整数为 ；如果直到遍历结束也没有不配位元素，则缺失最小正整数为 。
实现代码
def firstMissingPositive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i]-1]:
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
for i in range(n):
if nums[i] != i+1:
return i+1
return n+1
复杂度分析
时间复杂度：在 Python 代码中，看似第 5 行是计算最密集的（嵌套循环），其所做的处理是交换两个元素以进行配位。由于数组的每个索引最多只会进行一次配位，因此此处代码最多被执行 次。另外还有两个 次 for 循环。所以该算法的时间复杂度为 。
空间复杂度：由于我们在原数组 上进行操作，因而没有额外的空间申请。所以该算法的空间复杂度为 。
总结
虽说本题实现的代码量并不多，但思考起来却不算容易。关键点就在于要想到使数组有序和缺失最小正整数的范围。只要明确这两点，这个问题就会迎刃而解。
OK，本篇讲解到此结束了，有喜欢的小伙伴请点赞收藏哦，有问题的读者请评论或留言。如果文章有任何技术性问题，欢迎大佬指点~
链接：https://mp.weixin.qq.com/s/tY8g21DQicRZSuCPIxe9_g
（版权归原作者所有，侵删）
微信扫码关注该文公众号作者