LC41　缺失的第一个正数¶

困难通过率 49.7%python3核心代码模式普通数组样例通过牛客 AC数组哈希表

一句话

把值 v 原地换回下标 v-1，再扫一遍找第一个对不上号的位置。

解题思路¶

这题考什么¶

答案的取值范围先框死：数组长度为 n，就算 nums 恰好装着 1..n，缺的也只能是 n + 1；只要 1..n 里有任何一个没出现，答案就是其中最小的那个。所以答案必落在 [1, n + 1] 这 n + 1 个数里，而值域 [-2^31, 2^31 - 1] 里其余的数（负数、0、大于 n 的数）对答案毫无贡献，可以整体忽略。

于是问题变成「1..n 里哪个数没出现」。用哈希集合一句话就能答，但那是 O(n) 额外空间，题目要求常数级。突破口是：待查的键正好是 1..n，而数组本身正好有 n 个格子—— 数组自己就能当哈希表，约定「值 v 存放在下标 v - 1」，这个下标偏移的来源是下标从 0 开始而正整数从 1 开始。把每个能归位的值换到自己的格子上（这一步叫原地置换 / cyclic sort），再从左到右找第一个 nums[i] != i + 1 的位置，i + 1 就是答案；全都对得上就返回 n + 1。数组当哈希表的这类技巧见序列与数组，桶的思路见桶计数与离散化。

置换为什么是 O(n) 而不是 O(n^2)：内层 while 每成功交换一次，就有一个值永久落到了自己的正确格子上（此后再不会被换走），这样的事件全程最多发生 n 次。外层 n 步加上内层总计 n 次交换，合起来 O(n)。

数据规模与复杂度¶

1 <= n <= 1e5，-2^31 <= nums[i] <= 2^31 - 1。时间 O(n)，空间 O(1)（只用了几个整数变量，且直接改写入参）。排序后再扫是 O(n log n)，1e5 下也能过，但不满足题目点名的 O(n)；开一个长度 n + 2 的计数数组是 O(n) 时间但 O(n) 空间，同样不合要求。

坑在哪¶

置换循环的终止条件按「值」判，不能按「下标」判。写成 while 1 <= nums[i] <= n and nums[i] != i + 1 时，遇到重复值就死循环： nums = [1, 1] 的下标 1 处，值 1 想回下标 0，可下标 0 已经是 1，换过去还是原样，条件永远成立。本题解判的是目标格子里是不是已经放着这个值 （nums[v - 1] != v）——已经放着就说明这个值是重复的，直接罢手。
交换要用先取值再写两次的写法。写成 nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i] 是错的： Python 的多重赋值从左到右依次落地，左边第一项先把 nums[i] 改掉，第二项的下标 nums[i] - 1 于是用的是新值，换到了别的格子上。本题解先把 v = nums[i] 存下来，两次写入的下标都不受影响。
越界值（负数、0、大于 n）不要跳过循环之外另作处理。它们没有自己的格子，留在原地即可——最终扫描时它们所在的位置必然 nums[i] != i + 1，那个位置反而正是答案。
最后一趟扫描必须从左往右并在第一个不匹配处立刻返回，求的是「最小」的缺失值。
全部匹配时返回 n + 1，别漏。nums = [1, 2, 3] 的答案是 4，不是 3。
严格比对：答案是唯一的一个整数，没有多解。
本题解会改写入参 nums。这在力扣是允许的（判题只看返回值），但如果把这份代码搬到别处、调用方之后还要用原数组，就得先复制一份。

样例复核¶

nums = [3, 4, -1, 1]，n = 4，期望 2。置换过程（每行给出这一步之后的整个数组）：

i=0  nums[0]=3，应去下标 2，那里是 -1，交换      -> [-1, 4, 3, 1]
     nums[0] 变成 -1，不在 [1, 4] 内，停手
i=1  nums[1]=4，应去下标 3，那里是 1，交换       -> [-1, 1, 3, 4]
     nums[1] 变成 1，应去下标 0，那里是 -1，交换 -> [1, -1, 3, 4]
     nums[1] 变成 -1，停手
i=2  nums[2]=3，目标格子 nums[2] 已经是 3，停手  -> [1, -1, 3, 4]
i=3  nums[3]=4，目标格子 nums[3] 已经是 4，停手  -> [1, -1, 3, 4]

终态 [1, -1, 3, 4]。从左扫：下标 0 是 1（对得上），下标 1 是 -1（应为 2，对不上），返回 1 + 1 = 2，与样例一致。

参考实现¶

solutions/leetcode/LC41/sol.py
from typing import List, Optional


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        # 第一趟：原地置换，把每个落在 [1, n] 的值 v 送回下标 v - 1。
        # 下标偏移 -1 是因为下标从 0 起、正整数从 1 起
        for i in range(n):
            # 终止条件按**值**判：目标格子 nums[v - 1] 已经装着 v，
            # 说明这个值是重复的（或本来就归好位了），再换也是原样，必须停手，
            # 否则 nums = [1, 1] 会在这里死循环
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                # 先把值存下来再写：多重赋值从左往右落地，
                # 直接写 nums[i], nums[nums[i] - 1] = ... 会让第二个下标用到被改过的 nums[i]
                v = nums[i]
                # 循环不变量：每成功换一次，v 就永久落在自己的格子上，
                # 此后不会再被换走，所以全程交换次数不超过 n，总体仍是 O(n)
                nums[i] = nums[v - 1]
                nums[v - 1] = v
        # 第二趟：从左往右找第一个「格子里不是它该放的数」的位置。
        # 必须从左扫且立刻返回，求的是最小的缺失正整数
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        # 走到这里说明 1..n 全部就位，缺的是紧接着的 n + 1
        return n + 1

LC41 缺失的第一个正数¶