题目地址：First Missing Positive - LeetCode
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Note:
Your algorithm should run in O(n) time and uses constant extra space.
这道题目跟这道很像：LeetCode 31. Next Permutation-- Python 解法–数学题–比当前数大的最小的数
但这道题目难度明显更大，因为没有明确数组大小，而且有负数。
首先，时间复杂度至少为O(N)，因为要遍历数组一遍，空间复杂度可大可小，但O(N)的复杂度是可以接受的。
首先确定数组长度，最小缺失的正整数最大为N+1
遍历数组，使用bitmap确认存这个数是否存在过
Python解法如下：
class Solution:
def firstMissingPositive(self, nums) -> int:
length = len(nums)
l = [0]*(length+2)
for i in nums:
if 0 < i < 1 + length:
l[i] = 1
for i in range(1, length+3):
if l[i] == 0:
return i
此解法时间复杂度为O(n)，空间复杂度为O(n)。
想要空间复杂度降为O(1)是可以做到的，但不一定会更快，因为CPU缓存的原因，到处交换数组不一定快：
class Solution:
def firstMissingPositive(self, nums) -> int:
end = len(nums)
i = 0
while i != end:
val = nums[i]
if val == i+1:
i += 1
elif val > end or val <= 0 or nums[val-1] == val:
end -= 1
nums[i], nums[end] = nums[end], nums[i]
else:
nums[i], nums[val-1] = nums[val-1], nums[i]
return i+1
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
