41. 缺失的第一个正数

题目链接：41. 缺失的第一个正数

题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你设计并实现时间复杂度为 $O(n)$ 并且只使用常数级别额外空间的算法解决此问题。

核心思考：置换法（原地哈希）

本题的难点在于 $O(n)$ 时间和 $O(1)$ 空间的硬性指标。如果允许额外空间，哈希表可以轻易解决。为了满足原地（In-place）要求，我们可以把数组本身当成哈希表。

1. 核心逻辑：我们要找的是第一个缺失的正数。对于一个长度为 $L$ 的数组，这个正数一定在范围 $[1, L+1]$ 之内。我们可以通过置换，让每一个数字 $x$（如果在范围 $[1, L]$ 内）都回到它对应的“柜位” $x-1$。
2. 交换过程：
   • 遍历数组，对于每个位置的数 nums[i]，如果它是一个“合法”的正数（即在 $[1, L]$ 范围内），且它目前所在的位置不对（即 nums[i] != nums[nums[i]-1]），我们就将其与它目标位置上的数进行交换。
   • 这是一个“各回各家”的过程。注意使用 while 而非 if，因为交换回来的那个新数可能也需要继续交换到它对应的位子。
3. 最终检查：
   • 再次遍历数组，第一个满足 nums[i] != i + 1 的索引 i，对应的缺失值就是 i + 1。
   • 如果全部位置都对上了，说明缺失的是 L + 1。

解题思路 (Python)

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        l = len(nums)
        # 1. 置换：将数字 x 放到 nums[x-1] 的位置
        for i in range(l):
            # 使用 while 循环，确保交换过来的数也能回到它的位置
            while 1 <= nums[i] <= l and nums[i] != nums[nums[i] - 1]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
            
        # 2. 扫描：找出第一个背离“柜位规律”的位置
        for i in range(l):
            if nums[i] != i + 1:
                return i + 1
        
        # 如果 1 ~ l 都在，返回 l + 1
        return l + 1

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。虽然有嵌套循环，但每个数字最多只会被交换到它的正确位置一次，总交换次数为 $O(N)$。
• 空间复杂度：$O(1)$。只在原始数组上进行修改，不需要额外的辅助空间。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

num1 num2 num3 ... numN

输入一行整数数组，以空格分隔。

完整代码：

import sys

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
    l = len(nums)
            # 1. 置换：将数字 x 放到 nums[x-1] 的位置
            for i in range(l):
                # 使用 while 循环，确保交换过来的数也能回到它的位置
                while 1 <= nums[i] <= l and nums[i] != nums[nums[i] - 1]:
                    j = nums[i] - 1
                    nums[i], nums[j] = nums[j], nums[i]

            # 2. 扫描：找出第一个背离“柜位规律”的位置
            for i in range(l):
                if nums[i] != i + 1:
                    return i + 1

            # 如果 1 ~ l 都在，返回 l + 1
            return l + 1

def main():
    nums = list(map(int, sys.stdin.read().strip().split()))

    sol = Solution()
    result = sol.firstMissingPositive(nums)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo "2 -1 3 4 -5" | python solution.py