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

这道题要求我们在一个未排序的整数数组中，找出没有出现的最小的正整数。你的算法时间复杂度应为 O(n)，并且只能使用常数级别的额外空间。这是一个将哈希思想与数组下标就地结合使用的经典问题。

题目描述

给你一个未排序的整数数组 nums。请你找出其中没有出现的最小的正整数。
你必须实现时间复杂度为 O(n)、空间复杂度为 O(1) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,0]
输出：3

解释：最小的正整数 1 和 2 都在数组中，所以没有出现的最小正整数是 3。

示例 2：

输入：nums = [3,4,-1,1]
输出：2

解释：1 在数组中，但 2 没有出现。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

解释：所有数都大于 0，但最小的正整数 1 没有出现。

解题思路

如果允许使用额外空间，我们可以很容易地用哈希集合（HashSet）存储所有正数，然后从 1 开始逐个检查是否在集合中。但题目要求 O(1) 空间，所以我们需要一种“原地哈希”的技巧：利用数组自身的下标来标记某个正整数是否出现过。

核心观察：

1. 对于长度为 n 的数组，没有出现的最小的正整数只可能在 [1, n+1] 这个范围内。
   • 最理想情况：数组正好包含 1 到 n 的所有数，那么答案是 n+1。
   • 其他情况：在 [1, n] 范围内至少缺失一个数，答案就是那个缺失的最小数。
2. 因此，我们只需要关心数组中值在 [1, n] 范围内的数。

原地哈希策略：
我们可以遍历数组，对于每个遍历到的值 x，如果 x 在 [1, n] 范围内，我们就把它放到数组下标 x-1 的位置上（因为数组下标从 0 开始）。这样，如果数组中包含 1，它最终会在下标 0 处；包含 2，会在下标 1 处，以此类推。

遍历完成后，我们再次检查数组。如果某个下标 i 处的值不是 i+1，那么就说明 i+1 这个正整数缺失了。如果所有 [1, n] 都出现在正确位置，那么答案就是 n+1。

循序渐进讲解解题步骤

步骤 1：理解数据范围与目标

• 数组长度为 n。
• 答案只可能是 1 到 n+1 之间的整数。
• 我们要做的是“归位”：让数字 1 放到索引 0 处，数字 2 放到索引 1 处，……，数字 n 放到索引 n-1 处。

步骤 2：第一次遍历——原地交换归位

我们从头到尾遍历数组，对于每个位置 i：

1. 设当前值 x = nums[i]。
2. 如果 x 在 [1, n] 范围内，并且 x 不在它应该在的位置（即 nums[x-1] != x），那么我们就交换 nums[i] 和 nums[x-1]，把 x 放到正确的位置。
3. 交换后，新的 nums[i] 可能还是一个需要归位的数，所以我们需要继续处理当前位置 i，直到 nums[i] 不在 [1, n] 范围内，或者已经在正确位置。

为什么是 while 循环而不是 if？
因为交换后，被换到位置 i 的新数字可能也属于 [1, n] 且不在正确位置，需要继续归位。

为什么条件要加 nums[x-1] != x？
避免重复交换导致死循环。例如数组 [1, 1]，如果第一个 1 已经在正确位置，第二个 1 过来时，如果不检查就直接交换，就会和自身交换，无限循环。

示例推演：
数组 nums = [3, 4, -1, 1]，n = 4。

• i=0, x=3，它应该在索引 2（因为 3-1=2）。交换 nums[0] 和 nums[2]，数组变为 [-1, 4, 3, 1]。新 nums[0] = -1 不在 [1,4] 内，继续 i=1。
• i=1, x=4，应在索引 3。交换 nums[1] 和 nums[3]，数组变为 [-1, 1, 3, 4]。新 nums[1] = 1，应在索引 0，且 nums[0] != 1，所以继续 while：交换 nums[1] 和 nums[0]，数组变为 [1, -1, 3, 4]。新 nums[1] = -1，结束。
• i=2, x=3，已在正确位置（因为 nums[2] = 3），跳过。
• i=3, x=4，已在正确位置，跳过。
  最终数组：[1, -1, 3, 4]。

步骤 3：第二次遍历——查找第一个缺失的正数

遍历索引 0 到 n-1：

• 如果 nums[i] != i+1，那么 i+1 就是缺失的最小正整数，直接返回。
• 如果遍历完都没有找到，说明数组包含了 1 到 n 的所有数，返回 n+1。

在上面的示例数组 [1, -1, 3, 4] 中：

• i=0: nums[0] = 1，正确。
• i=1: nums[1] = -1，不等于 2，所以缺失的最小正整数是 2，返回 2。

步骤 4：边界情况与复杂度分析

• 时间复杂度：每个数字最多被交换一次放到正确位置，所以尽管有 while 循环，总交换次数不超过 n，时间复杂度 O(n)。
• 空间复杂度：只用了几个变量，O(1)。
• 边界情况：空数组？题目未明确，但按定义最小正整数是 1，所以空数组应返回 1。
• 包含重复数字：我们的条件 nums[x-1] != x 能防止重复数字导致的死循环，重复数字最终会让正确位置放上该数字，其他重复数字留在外面（不在 [1, n] 内或不在正确位置）。

完整代码示例（Python）

def firstMissingPositive(nums):
    n = len(nums)
    if n == 0:
        return 1
    
    i = 0
    while i < n:
        # 当前值在 [1, n] 范围内，且不在它应该在的位置
        if 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # 交换到正确位置
            correct_idx = nums[i] - 1
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1
    
    # 第二次遍历，查找第一个位置不匹配的
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    
    return n + 1

测试运行：

print(firstMissingPositive([3, 4, -1, 1]))  # 输出 2
print(firstMissingPositive([1, 2, 0]))      # 输出 3
print(firstMissingPositive([7, 8, 9, 11, 12]))  # 输出 1

总结

这道题的关键在于利用数组下标本身作为哈希表，将数值 x 映射到下标 x-1 的位置上，从而在 O(1) 空间内标记数字是否出现。这种“原地哈希”技巧在限制空间复杂度的问题中非常有用，是哈希思想的一种巧妙变体。通过两次遍历（一次归位，一次检查），我们就能在 O(n) 时间、O(1) 空间内解决问题。