C++未排序数组首个缺失正整数解法理解咨询

我来帮你拆解这个经典的「寻找未排序数组中首个缺失正整数」的O(n)时间、O(1)空间解法，把每一步的逻辑和你困惑的标记部分讲得明明白白～

首先要明确一个关键结论：对于长度为n的数组，最小的缺失正整数一定在[1, n+1]这个区间里。为什么？假设数组包含了1到n的所有正整数，那缺失的就是n+1；如果有某个数不在1到n里，那缺失的就是那个最小的数。这个结论是整个解法的基础，能帮我们把注意力集中在有效范围内，忽略那些无关的数（比如负数、0、大于n的数）。

步骤1：预处理数组，清除无效值 #

你提到的“用特殊正值标记负数”其实是预处理的核心：把数组里所有非正整数（负数、0）以及大于n的数都替换成n+1（或者任何比n大的正数）。这么做的原因是，这些数不可能是我们要找的“最小缺失正整数”，而且后续标记的时候，它们不会干扰我们对1~n范围的判断。

举个例子，数组[3,4,-1,1]，n=4，预处理后变成[3,4,5,1]（把-1换成5）。

步骤2：检查基础情况+用负数标记存在的正整数 #

先快速判断：数组里有没有1？ #

如果数组里完全没有1，那最小缺失的正整数直接就是1，这一步可以提前返回，节省时间。比如数组[-2,3,4]，直接返回1就行。

核心标记逻辑：用负数标记“该正整数已存在” #

这部分应该是你最困惑的地方，我用例子一步步讲：

• 遍历预处理后的数组，对每个元素x：
  1. 先取x的绝对值abs_x（因为之前可能已经被标记成负数了，要取原始值）
  2. 如果abs_x在1~n之间，说明这个数是我们要关注的正整数，那么找到数组中索引为abs_x - 1的位置（因为正整数1对应索引0，2对应索引1，以此类推）
  3. 把这个索引位置的数变成负数（如果它本来就是负数，就保持不变，不用再处理）

为什么这么做？因为负数就代表“对应的正整数已经在数组里出现过”。比如索引0的数是负数，说明正整数1存在；索引1的数是负数，说明正整数2存在，以此类推。

还是用刚才的例子[3,4,5,1]（n=4）：

1. 第一个元素是3，abs_x=3，在1~4之间，找到索引3-1=2的位置，把5改成-5 → 数组变成[3,4,-5,1]
2. 第二个元素是4，abs_x=4，找到索引4-1=3的位置，把1改成-1 → 数组变成[3,4,-5,-1]
3. 第三个元素是-5，abs_x=5，大于4，跳过
4. 第四个元素是-1，abs_x=1，找到索引1-1=0的位置，把3改成-3 → 数组变成[-3,4,-5,-1]

步骤3：扫描数组，找到首个缺失的正整数 #

遍历处理后的数组，找到第一个正数所在的索引，这个索引+1就是我们要找的最小缺失正整数：

• 例子里的数组是[-3,4,-5,-1]，第二个元素（索引1）是正数，所以返回1+1=2，正好是正确答案。
• 如果数组所有元素都是负数，说明1~n的正整数都存在，返回n+1。比如数组[1,2,3]，处理后是[-1,-2,-3]，返回3+1=4。

def firstMissingPositive(nums):
    n = len(nums)
    
    # 步骤1：预处理，替换无效值
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = n + 1
    
    # 步骤2：用负数标记存在的正整数
    for i in range(n):
        abs_x = abs(nums[i])
        if abs_x <= n:
            # 把对应索引的数变成负数，注意要取绝对值再变负，避免重复标记
            nums[abs_x - 1] = -abs(nums[abs_x - 1])
    
    # 步骤3：寻找第一个正数的索引
    for i in range(n):
        if nums[i] > 0:
            return i + 1
    
    # 所有1~n都存在，返回n+1
    return n + 1

其实这个思路类似原地计数排序：我们不需要额外的数组来记录每个正整数是否存在，而是直接利用原数组的空间——用每个位置的正负状态来存储“对应正整数是否存在”的信息。

举个更简单的例子：数组[2,1,0]，n=3：

1. 预处理后变成[2,1,4]
2. 遍历第一个元素2，abs_x=2，把索引1的数改成-1 → [2,-1,4]
3. 遍历第二个元素-1，abs_x=1，把索引0的数改成-2 → [-2,-1,4]
4. 遍历第三个元素4，跳过
5. 扫描数组，第三个元素（索引2）是正数，返回2+1=3，正确。

这里的负数就像是一个“已打卡”的标记：只要某个正整数x存在，x对应的位置（x-1）就会被标记为负数，后续扫描时看到正数，就说明对应的x（索引+1）从未被“打卡”，也就是缺失的最小正整数。

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