image.png
0. 链接
1. 题目
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.
2. 思路：先排除异常值+标记具有合法标记的值+逐个排查得到结果
- 如果一个数字都不缺, 则每个值都处于
[1, n]之间, 所以首先想到的是，将原始数组的值与数组下标建立映射，而对非正数和超过n的数，直接忽略； - 由于只允许O(n)的time和O(1)的space, 所以需要常数次遍历(为了满足O(n) time)，而且需要在原始数组上直接修改(为了满足O(1)的space), 这里采用标记法:
2.1 第一次遍历，将负数和超出上限的数设置为0
2.2 第二次遍历，对每个正整数值所对应下标序号处的值，加上n+1，这次遍历完成后，从前到后，具有合法值的下标处，都被加上了n+1，所以第3步只需要找出第一个小于n+1的值所在下标+1就是答案了
2.3 第三次遍历，找到首个小于n+1的就是答案 - 找遍了也找不到，说明给出的数组不缺整数值，则返回n+1.
3. 代码
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
length = len(nums)
up_bound = length + 1
for i in range(length):
if nums[i] < 0 or nums[i] > length:
nums[i] = 0
for i in range(length):
target_idx = nums[i] % up_bound - 1
if target_idx >= 0 and nums[target_idx] < up_bound:
nums[target_idx] += up_bound
for i in range(length):
if nums[i] < up_bound:
return i + 1
return up_bound
solution = Solution()
print(solution.firstMissingPositive([3, 4, -1, 1]))
print(solution.firstMissingPositive([1, 2, 0]))
print(solution.firstMissingPositive([7, 8, 9, 11, 12]))
输出结果
2
3
1
4. 结果
image.png
