2018 年第 41 题

题目描述

给定一个长度为 n 的整数数组，请设计一个时间复杂度尽可能低、额外空间尽可能少的算法，找出数组中没有出现过的最小正整数。

例如：

[3, 4, -1, 1] -> 2
[1, 2, 0] -> 3

解题思路

关键观察：

• 若答案在 1..n 之间，则值 x 最好放在下标 x - 1 的位置。

所以可以使用“原地哈希”：

1. 扫描数组，对每个 nums[i]，只要它在 1..n 范围内，且没有放到正确位置，就把它交换到 nums[nums[i] - 1] 上。
2. 调整结束后，再从左到右扫描。
3. 第一个 nums[i] != i + 1 的位置，其答案就是 i + 1。
4. 若都匹配，则答案是 n + 1。

手算示例

数组：[3, 4, -1, 1]

初始：[3, 4, -1, 1]

3 应该放到下标 2：
[-1, 4, 3, 1]

4 应该放到下标 3：
[-1, 1, 3, 4]

1 应该放到下标 0：
[1, -1, 3, 4]

再次扫描：
下标 0 是 1，正确
下标 1 不是 2

答案：2

Python 实现

def first_missing_positive(nums):
    n = len(nums)

    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            correct = nums[i] - 1
            nums[i], nums[correct] = nums[correct], nums[i]

    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

易错点

• 交换必须写成 while，因为换过来的新数也可能还要继续归位。
• 负数、0、越界正数都不参与归位。
• 一定要判断 nums[nums[i] - 1] != nums[i]，否则会死循环。

对应题

来源	题目	相似度	主要差异
LeetCode	41. 缺失的第一个正数	100%	基本一致

难度

⭐️⭐️⭐️⭐️