【LeetCode 热题 100】41. 缺失的第一个正数——（解法二）原地哈希

Problem: 41. 缺失的第一个正数
题目：给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

【LeetCode 热题 100】41. 缺失的第一个正数——（解法一）暴力解

整体思路

这段代码旨在高效地解决 “缺失的第一个正数” 问题。与上一个排序解法不同，此版本采用了一种称为 “原地哈希” (In-place Hashing) 或 “循环排序” (Cyclic Sort) 的思想，能够在 O(N) 的时间复杂度和 O(1) 的空间复杂度内完成任务，是此问题的最优解。

算法的核心思想是：尝试将每个数字 x 放到它“应该”在的位置上。对于一个长度为 n 的数组，如果我们只关心 1 到 n 的正整数，那么数字 1 应该在索引 0 的位置，数字 2 应该在索引 1 的位置，以此类推，数字 x 应该在索引 x-1 的位置。

算法的执行步骤如下：

1. 原地重排数组：

   • 算法通过一个 for 循环遍历数组。在 for 循环的内部，是一个 while 循环，这是算法的核心。
   • 对于当前位置 i 的数字 nums[i]：
     • while 循环的条件：这个条件非常关键，它同时检查三件事：
       1. nums[i] >= 1 && nums[i] <= n：确保 nums[i] 是一个在 [1, n] 范围内的有效正数。我们只关心这些数字，任何超出这个范围的数字（负数、零、或大于 n 的数）都无需处理，因为它们不可能是 1 到 n 范围内的缺失正数。
       2. nums[i] != nums[nums[i] - 1]：检查 nums[i] 是否已经在它正确的位置上。nums[i] 应该在的位置是 nums[i] - 1。如果 nums[i] 的值不等于 nums 在 nums[i]-1 索引上的值，说明 nums[i] 还未归位。
     • 执行交换：如果 while 条件满足，就执行一次交换，将 nums[i] 与 nums[nums[i] - 1] 的值互换。这个操作的目的就是将 nums[i] 送到它应该在的位置去。
   • 这个 while 循环会持续进行，直到当前 i 位置的数字不再满足交换条件（可能因为它已经归位，或者它是一个无效数字）。然后外层 for 循环才会进入下一个 i。

2. 查找缺失的正数：

   • 当第一步的重排完成后，理想情况下，数组 nums 应该形如 [1, 2, 3, ..., n]。
   • 接着，进行第二次遍历。在这个遍历中，检查每个位置 i 的值是否等于 i+1。
   • 如果 nums[i] != i + 1，这意味着 i+1 这个正整数本应在这里，但它不在。由于我们已经把所有能归位的数字都归位了，这个不在位置上的 i+1 就是我们找到的第一个缺失的正数。直接返回 i+1。

3. 处理特殊情况：

   • 如果在第二次遍历中，所有的数字都在它们正确的位置上（即 nums 就是 [1, 2, ..., n]），那么循环会正常结束。
   • 这说明 1 到 n 所有的正数都存在，因此，缺失的第一个正数就是 n+1。

完整代码

class Solution {
    /**
     * 在一个未排序的整数数组中，找到没有出现的最小的正整数。
     * 采用原地哈希/循环排序的方法。
     * @param nums 输入的整数数组
     * @return 缺失的最小正整数
     */
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // 步骤 1: 原地重排数组，尝试将每个数字放到它正确的位置上。
        // 数字 x 应该在索引 x-1 的位置。
        for (int i = 0; i < n; i++) {
            // 当 nums[i] 在 [1, n] 范围内，并且它没有在正确的位置上时，循环交换。
            // 正确的位置是指：nums[i] 的值应该等于索引 nums[i]-1 上的值。
            // 例如，如果 nums[i] = 3，它应该在索引 2 的位置，即 nums[2] 的值应该是 3。
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                // 将 nums[i] 与它目标位置上的数进行交换。
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        
        // 步骤 2: 查找第一个不满足 nums[i] == i + 1 的位置。
        for (int i = 0; i < n; i++) {
            // 如果在索引 i 上的值不是 i+1，那么 i+1 就是第一个缺失的正数。
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        // 步骤 3: 如果 1 到 n 都存在，那么缺失的第一个正数就是 n+1。
        return n + 1;
    }
}

时空复杂度

时间复杂度：O(N)

1. for 和 while 循环：虽然代码中有一个嵌套的 while 循环，但它的总执行次数并不是 O(N^2)。
2. 均摊分析：
   • 关键在于，每一次 while 循环中的成功交换，都会将至少一个数字（即 nums[nums[i] - 1] 被换过来的那个）放到了它最终正确的位置上。
   • 一个数字一旦被放到正确的位置，它就不会再参与后续的交换了（因为 nums[i] == nums[nums[i] - 1] 条件会使其不满足 while 循环）。
   • 由于数组中只有 N 个位置，最多只会发生 N 次成功的交换。
   • 因此，所有 while 循环的总执行次数（包括成功的交换和不成功的检查）加起来是 O(N) 级别的。外层 for 循环也执行 N 次。所以这部分的复杂度是 O(N)。
3. 第二次遍历：最后的 for 循环遍历数组一次，时间复杂度为 O(N)。

综合分析：
算法的总时间复杂度是 O(N) + O(N) = O(N)。

空间复杂度：O(1)

1. 主要存储开销：该算法直接在输入数组 nums 上进行修改，没有创建任何与输入规模 N 成比例的新的数据结构。
2. 辅助变量：只使用了 n, i, temp 等几个常数级别的整型变量。

综合分析：
算法所需的额外辅助空间是常数级别的。因此，其空间复杂度为 O(1)。这是该问题最优的空间效率。

参考灵神