算法题--寻找缺失的最小正整数

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. 如果一个数字都不缺, 则每个值都处于[1, n]之间, 所以首先想到的是，将原始数组的值与数组下标建立映射，而对非正数和超过n的数，直接忽略；
2. 由于只允许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的就是答案
3. 找遍了也找不到，说明给出的数组不缺整数值，则返回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