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

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

整体思路

这段代码旨在解决一个经典的数组问题：缺失的第一个正数 (First Missing Positive)。问题要求在一个未排序的整数数组中，找到没有出现的最小的正整数。例如，在 [3, 4, -1, 1] 中，最小的缺失正数是 2。

该算法采用了一种简单直观的 “排序后线性扫描” 的策略。其核心逻辑步骤如下：

1. 排序：

   • 算法的第一步是对整个输入数组 nums 进行升序排序。
   • 目的：排序是这个解法的关键前提。它将所有负数、零和重复的正数都组织起来，更重要的是，它使得我们可以按顺序查找 1, 2, 3, ...。一旦排好序，如果这些正整数存在，它们必然会以（可能不连续的）升序出现。

2. 线性扫描与目标追踪：

   • 算法使用一个变量 ans，初始化为 1。这个 ans 变量可以被看作是“我们正在寻找的目标正整数”。
   • 接着，通过一个 for 循环遍历排序后的数组。
   • 在循环中，将数组中的当前元素 nums[i] 与我们的目标 ans 进行比较。
     • 如果 nums[i] == ans：这意味着我们找到了当前的目标 1（或 2, 3, …）。因此，我们需要更新我们的目标为下一个正整数，即执行 ans++。
     • 如果 nums[i] != ans：这可能是因为 nums[i] 是一个负数、零、或者是一个比 ans 更大的正数，也可能是重复的数字。在任何这些情况下，我们都还没有找到当前的目标 ans，所以我们保持 ans 不变，继续向后查找。

3. 返回结果：

   • 当遍历完整个数组后，ans 的值就是最小的、没有在数组中找到的那个正整数。例如，如果数组中有 1 和 2，ans 会被更新到 3。如果在后续的遍历中没有找到 3，那么 ans 最终就会停在 3，这正是我们想要的结果。

总而言之，这是一个逻辑简单、易于理解但时间效率不是最优的解法，因为其性能瓶颈在于排序步骤。

完整代码

class Solution {
    /**
     * 在一个未排序的整数数组中，找到没有出现的最小的正整数。
     * @param nums 输入的整数数组
     * @return 缺失的最小正整数
     */
    public int firstMissingPositive(int[] nums) {
        // ans: 我们的“目标”或“候选”的最小缺失正整数，从 1 开始寻找。
        int ans = 1;
        
        // 步骤 1: 对数组进行升序排序。
        // 这使得我们可以按顺序查找 1, 2, 3, ...
        Arrays.sort(nums);
        
        // 步骤 2: 线性扫描排序后的数组
        for (int i = 0; i < nums.length; i++) {
            // 如果在数组中找到了我们当前的目标 (ans)，
            // 说明 ans 不是缺失的，我们需要寻找下一个正整数。
            if (nums[i] == ans) {
                // 更新目标为下一个正整数
                ans++;
            }
        }
        
        // 遍历结束后，ans 的值就是第一个没有在数组中匹配到的正整数。
        return ans;
    }
}

时空复杂度

时间复杂度：O(N log N)

1. 排序：Arrays.sort(nums) 是算法中时间开销最大的部分。在Java中，对基本类型数组的排序采用的是双轴快速排序（Dual-Pivot Quicksort），其平均时间复杂度为 O(N log N)。
2. 线性扫描：for 循环遍历整个数组一次，执行 N 次迭代。循环体内部的操作（比较和可能的自增）都是 O(1) 的。因此，这部分的时间复杂度是 O(N)。

综合分析：
算法的总时间复杂度由排序和线性扫描两部分构成，即 O(N log N) + O(N)。在 Big O 表示法中，我们只保留最高阶项，因此最终的时间复杂度由排序决定，为 O(N log N)。

空间复杂度：O(log N)

1. 主要存储开销：该算法在原地修改数组（通过排序），并没有创建与输入规模 N 成比例的新的数据结构。
2. 排序的额外空间：
   • Java 的 Arrays.sort 实现（双轴快速排序）是一种原地排序算法，但它需要递归。递归调用会占用调用栈（call stack）的空间。
   • 对于一个性能良好的快速排序实现，递归栈的深度在平均情况下是 O(log N)，在最坏情况下可能达到 O(N)。
3. 其他变量：ans 和 i 等变量只占用常数级别的空间，即 O(1)。

综合分析：
算法所需的额外辅助空间主要由排序算法的递归调用栈决定。因此，在平均情况下，其空间复杂度为 O(log N)。如果忽略排序算法内部的栈空间，可以认为是 O(1)，但 O(log N) 是一个更精确的分析。

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