BM53　缺失的第一个正整数¶

中等通过率 34.78%python3核心代码模式样例通过牛客 AC数组哈希

牛客原题　源码

讲解章节：哈希表

一句话

原地置换把数字 v 送回下标 v-1，再扫一遍找第一个错位。

解题思路¶

这题考什么¶

两个观察合起来就是全部解法。

其一，答案的取值范围。长度为 n 的数组最多装下 1 到 n 这 n 个正整数，装满时答案是 n+1，否则 1 到 n 里必有缺口。答案一定落在 [1, n+1]，因此所有小于等于 0 或大于 n 的数字都是噪音，可以直接无视。

其二，怎样在 O(1) 空间里做「某个数出现过没有」的查询。开哈希表就是 O(n) 空间，于是把数组自己当哈希表：约定「数字 v 应该待在下标 v-1」，即 nums[i] == i + 1。

第一遍原地置换归位，对每个位置 i 反复做——

当 1 <= nums[i] <= n 且 nums[i] 还没落在它该在的位置：
    把 nums[i] 换到下标 nums[i] - 1 上

第二遍从左往右找第一个 nums[i] != i + 1 的位置，答案就是 i + 1；全部归位则返回 n + 1。

数据规模与复杂度¶

0 <= len(nums) <= 5e5，元素填满 32 位有符号整数范围，时限其他语言 2 秒。外层扫描 n 次，内层的 while 看似嵌套，但每成功交换一次就有一个数字永久归位，整个过程的交换次数不超过 n，所以两遍加起来仍是 O(n)，约百万级基本操作。空间 O(1)：只用了下标变量，没有额外容器，正是题面进阶要求的那一项。改用集合判 1 到 n+1 哪个缺席，代码更短但空间退化到 O(n)。

坑在哪¶

内层的停止条件比较的是值（nums[nums[i]-1] != nums[i]），不是下标。题面写的是「无重复元素」，但题面的边界描述不构成担保；一旦真出现两个相同的数，按下标判会让这两个位置无休止地互换，程序卡死。按值判则第二个相同的数发现目标位置已经放着同样的值，立刻停手。
交换必须先把目标下标存进 j。若写成 nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]， Python 的多目标赋值从左往右生效：nums[i] 先被改写，第二个目标再去算 nums[i] - 1 时用的已经是新值，换到的位置是错的。
内层必须是 while，不能是 if。一次交换换回来的新数字往往同样需要归位： [3, 1, 2] 用 if 只换一次得到 [2, 1, 3]，2 停在下标 0 上，第二遍会误报答案 1，正解是 4。
范围判断不能省。元素可以取到 2 的 31 次方减一，不先卡住 1 <= nums[i] <= n 就会拿它当下标，直接越界。
空数组不需要特判：n = 0 时两个循环都不执行，直接返回 1。
这份写法原地修改入参。判题只取返回值，所以无妨；若调用方之后还要用原数组，得自己先复制一份。

样例复核¶

[-2, 3, 4, 1, 5]，n = 5。

i=1：3 换到下标 2，换回 4；4 换到下标 3，换回 1；1 换到下标 0，换回 -2，越界停手
此时数组是 [1, -2, 3, 4, 5]，i=2、3、4 都已归位
第二遍：下标 0 放着 1 正确；下标 1 应放 2 而实际是 -2  ->  答案 2

参考实现¶

solutions/nowcoder/BM53/sol.py
from typing import List, Optional


class Solution:
    def minNumberDisappeared(self, nums: List[int]) -> int:
        n = len(nums)
        # 第一遍：原地置换，把每个 1..n 的数字送回下标「值减一」的位置
        for i in range(n):
            # 只搬有效范围内的数；比较值而非下标，重复值不会来回死换
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                # 先把目标下标取出来。直接写成双目标赋值会先改掉 nums[i]，右边的下标随之算错
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
        # 第二遍：第一个没归位的下标就是缺口，答案是它的「应有值」
        for i in range(n):
            if nums[i] != i + 1:        # 下标 i 上没坐着 i+1，说明 i+1 缺席
                return i + 1
        return n + 1                    # 1..n 全部到齐，缺的只能是 n+1

BM53 缺失的第一个正整数¶