哈希算法题目：缺失的第一个正数

题目描述
给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。
要求：你的算法的时间复杂度应为 O(n)，并且只能使用常数级别的额外空间。

示例 1
输入：nums = [1,2,0]
输出：3
解释：数组中缺失的最小正整数是 3。

示例 2
输入：nums = [3,4,-1,1]
输出：2
解释：数组中缺失的最小正整数是 2。

示例 3
输入：nums = [7,8,9,11,12]
输出：1
解释：数组中缺失的最小正整数是 1。

解题思路
这个问题的挑战在于时间复杂度和空间复杂度的限制。一个直观的想法是使用哈希集合来记录出现过的数字，然后从 1 开始逐个检查。但使用哈希集合需要 O(n) 的额外空间，不符合“常数级别额外空间”的要求。因此，我们需要一种方法，能够“就地”记录数字的出现情况。

关键洞察
对于一个长度为 N 的数组，缺失的第一个正数一定在 [1, N+1] 这个范围内。

• 如果数组包含了 1 到 N 的所有数字，那么缺失的第一个正数就是 N+1。
• 否则，缺失的第一个正数一定在 1 到 N 之间。

因此，我们可以将数组本身视为一个哈希表，通过某种方式，让数组的索引和值建立一种映射关系，从而利用数组自身的空间来标记某个正整数是否出现。

循序渐进解题过程

步骤 1：核心思想——“座位归位法”
我们可以尝试将每个遇到的正整数 nums[i] 放到它“应该”在的位置上。什么是“应该”在的位置？如果一个数字是 x，并且 x 在 1 到 N 的范围内（1 <= x <= len(nums)），那么它应该被放在数组的索引为 x-1 的位置上（因为数组索引从 0 开始）。

例如：

• 数字 1 应该放在索引 0 的位置。
• 数字 2 应该放在索引 1 的位置。
• ...
• 数字 N 应该放在索引 N-1 的位置。

步骤 2：具体操作——“交换”
我们遍历数组，对于每个元素 nums[i]：

1. 检查它是否是一个在目标范围内的正数：1 <= nums[i] <= len(nums)。
2. 如果满足条件，我们检查这个数字是否已经坐在了它“正确”的座位上。即，nums[i] 是否等于 nums[nums[i] - 1]？
   • 如果相等，说明它已经在正确位置，或者出现了重复值（重复值我们只需要一个在正确位置即可），我们跳过。
   • 如果不相等，我们就进行交换：将 nums[i] 和它正确位置上（即索引为 nums[i]-1 的位置）的数字进行交换。

注意：交换后，新的 nums[i] 可能又是一个需要被放置到正确位置的正整数，所以我们需要在一个循环内持续进行此操作，直到 nums[i] 不再满足交换条件（即它不是 1 到 N 之间的数，或者它已经在了正确的位置）。

步骤 3：遍历检查
经过步骤 2 的“归位”处理后，我们再次遍历数组。这次我们检查每个位置 i 上的数字。

• 如果 nums[i] 不等于 i + 1，那么就说明 i + 1 这个正整数缺失了，它就是我们要找的答案。
• 如果遍历完整个数组，发现每个位置 i 上的数字都等于 i + 1，那就说明数组里包含了 1 到 N 的所有数字，那么缺失的第一个正数就是 N+1。

详细示例解析
让我们用示例 nums = [3, 4, -1, 1] 来走一遍流程。数组长度 N=4。

第一次遍历（归位过程）

• i = 0: nums[0] = 3。3 在 [1, 4] 范围内。它的正确位置是索引 2 (3-1=2)。现在 nums[2] 是 -1。3 和 -1 不相等，所以交换。数组变为：[-1, 4, 3, 1]。现在 nums[0] 是 -1，不满足交换条件，i++。
• i = 1: nums[1] = 4。4 在 [1, 4] 范围内。它的正确位置是索引 3 (4-1=3)。现在 nums[3] 是 1。4 和 1 不相等，所以交换。数组变为：[-1, 1, 3, 4]。现在 nums[1] 是 1。1 在 [1, 4] 范围内，它的正确位置是索引 0 (1-1=0)。现在 nums[0] 是 -1。1 和 -1 不相等，所以交换。数组变为：[1, -1, 3, 4]。现在 nums[1] 是 -1，不满足交换条件，i++。
• i = 2: nums[2] = 3。3 在 [1, 4] 范围内。它的正确位置是索引 2 (3-1=2)。现在 nums[2] 是 3。3 和 3 相等（已在正确位置），跳过。i++。
• i = 3: nums[3] = 4。4 在 [1, 4] 范围内。它的正确位置是索引 3 (4-1=3)。现在 nums[3] 是 4。4 和 4 相等（已在正确位置），跳过。

归位后的数组为：[1, -1, 3, 4]。

第二次遍历（检查过程）

• i = 0: nums[0] 是 1，等于 0+1。继续。
• i = 1: nums[1] 是 -1，不等于 1+1 (即2)。我们发现 2 缺失了。
  所以答案是 2。

代码实现要点（伪代码风格）

def firstMissingPositive(nums):
    n = len(nums)
    
    # 第一次遍历：归位过程
    i = 0
    while i < n:
        # 检查 nums[i] 是否在目标范围 [1, n] 内
        # 并且检查它是否不在正确的位置上
        if 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # 交换 nums[i] 和它正确位置上的数字
            correct_index = nums[i] - 1
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
            # 注意：交换后，i 不要自增，因为新的 nums[i] 可能还需要处理
        else:
            # 如果不需要交换，才移动到下一个元素
            i += 1

    # 第二次遍历：检查过程
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
            
    # 如果前 n 个位置都正确，则缺失的是 n+1
    return n + 1

复杂度分析

• 时间复杂度：O(n)。尽管代码中有嵌套循环，但每个数字最多被交换一次就能到达其正确位置，所以总操作次数是线性的。
• 空间复杂度：O(1)。只使用了常数级别的额外变量（如 i, n, correct_index）。

总结
这道题的精妙之处在于利用数组本身作为哈希表，通过“座位归位”的思想，在不使用额外空间的情况下，标记了哪些正整数已经出现。这是一种非常经典的“原地哈希”技巧。