求首个缺失的正整数：线性时间+常数空间解法咨询

嘿，我来给你掰扯清楚这个问题的解法，绝对用你能听懂的话讲透～

作为竞赛编程新手，这个问题的核心是把原数组当成“免费的哈希表”用——毕竟要求不能开额外空间，而且我们要找的数范围其实很有限（1到n+1，n是数组长度）。下面一步步拆解逻辑：

1. 先把无关的数“屏蔽”掉 #

我们要找的是最小的正整数，所以：

• 所有≤0的数（负数、0）肯定不是答案
• 所有大于n的数也不可能是答案（因为如果1到n都在数组里，答案就是n+1；如果有缺失，那缺失的数一定在1到n之间）

所以第一步，把数组里所有≤0或者>n的数，替换成n+1（这个数不在1到n的范围内，不会干扰后续判断）。

比如输入[3,4,-1,1]，n=4，替换后变成[3,4,5,1]。

2. 把每个正整数放到它“该待的位置” #

遍历数组，对于每个元素num：

• 如果num在1到n之间，那它的正确位置是索引pos = num - 1（因为1对应索引0，2对应索引1，以此类推）
• 交换当前元素和pos位置的元素，直到当前位置的元素要么不在1到n范围内，要么已经在正确的位置上
• 注意：如果arr[pos]已经等于num，说明是重复元素，直接跳过（不然会无限循环交换）

举个例子，处理[3,4,5,1]：

• 索引0的元素是3，pos=2，arr[2]=5≠3，交换后数组变成[5,4,3,1]。现在索引0的元素是5（>4），跳过。
• 索引1的元素是4，pos=3，arr[3]=1≠4，交换后数组变成[5,1,3,4]。现在索引1的元素是1，pos=0，arr[0]=5≠1，交换后数组变成[1,5,3,4]。现在索引1的元素是5（>4），跳过。
• 索引2的元素是3，pos=2，位置正确，跳过。
• 索引3的元素是4，pos=3，位置正确，跳过。

处理后数组是[1,5,3,4]。

3. 找第一个“位置不对”的元素 #

再次遍历数组，找到第一个索引i，满足arr[i] != i+1，那么i+1就是我们要找的首个缺失的正整数。

• 如果所有位置都满足arr[i] == i+1，说明1到n都存在，答案就是n+1。

比如处理后的[1,5,3,4]：

• 索引0：arr[0]=1 == 0+1，没问题
• 索引1：arr[1]=5 != 1+1=2 → 答案就是2，和例子完全一致。

再看另一个例子[1,2,0]：

• 第一步替换0为4，数组变成[1,2,4]
• 第二步遍历，所有元素都在正确位置（1在0，2在1，4>3）
• 第三步遍历，索引2的arr[2]=4 != 2+1=3 → 答案是3，正确。

为什么这个解法符合要求？ #

• 时间复杂度O(n)：每个元素最多被交换一次，交换后它就到了正确的位置，不会再被移动。加上两次遍历数组，总时间是线性的。
• 空间复杂度O(1)：只用到了几个临时变量，完全在原数组上操作，没有开辟额外的数组或哈希表。

伪代码示例 #

def firstMissingPositive(arr):
    n = len(arr)
    # 第一步：替换无关元素
    for i in range(n):
        if arr[i] <= 0 or arr[i] > n:
            arr[i] = n + 1
    # 第二步：放置元素到正确位置
    for i in range(n):
        num = arr[i]
        while 1 <= num <= n and arr[num - 1] != num:
            # 交换当前元素和它应该在的位置的元素
            arr[i], arr[num - 1] = arr[num - 1], arr[i]
            num = arr[i]  # 更新num为交换后的当前元素
    # 第三步：找缺失的数
    for i in range(n):
        if arr[i] != i + 1:
            return i + 1
    # 如果所有1~n都存在，返回n+1
    return n + 1

你可以把例子代入这段代码跑一遍，就能更直观地看到每一步的变化啦～

内容的提问来源于stack exchange，提问作者user8292826