Problem: 41. 缺失的第一个正数
题目：给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N log N)
- 空间复杂度：O(log N)
整体思路
这段代码旨在解决一个经典的数组问题：缺失的第一个正数 (First Missing Positive)。问题要求在一个未排序的整数数组中，找到没有出现的最小的正整数。例如，在 [3, 4, -1, 1] 中，最小的缺失正数是 2。
该算法采用了一种简单直观的 “排序后线性扫描” 的策略。其核心逻辑步骤如下：
-
排序：
- 算法的第一步是对整个输入数组
nums进行升序排序。 - 目的：排序是这个解法的关键前提。它将所有负数、零和重复的正数都组织起来，更重要的是，它使得我们可以按顺序查找
1, 2, 3, ...。一旦排好序，如果这些正整数存在，它们必然会以（可能不连续的）升序出现。
- 算法的第一步是对整个输入数组
-
线性扫描与目标追踪：
- 算法使用一个变量
ans，初始化为1。这个ans变量可以被看作是“我们正在寻找的目标正整数”。 - 接着，通过一个
for循环遍历排序后的数组。 - 在循环中，将数组中的当前元素
nums[i]与我们的目标ans进行比较。- 如果
nums[i] == ans：这意味着我们找到了当前的目标1（或2,3, …）。因此，我们需要更新我们的目标为下一个正整数，即执行ans++。 - 如果
nums[i] != ans：这可能是因为nums[i]是一个负数、零、或者是一个比ans更大的正数，也可能是重复的数字。在任何这些情况下，我们都还没有找到当前的目标ans，所以我们保持ans不变，继续向后查找。
- 如果
- 算法使用一个变量
-
返回结果：
- 当遍历完整个数组后，
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)
- 排序：
Arrays.sort(nums)是算法中时间开销最大的部分。在Java中，对基本类型数组的排序采用的是双轴快速排序（Dual-Pivot Quicksort），其平均时间复杂度为 O(N log N)。 - 线性扫描：
for循环遍历整个数组一次，执行N次迭代。循环体内部的操作（比较和可能的自增）都是 O(1) 的。因此，这部分的时间复杂度是 O(N)。
综合分析：
算法的总时间复杂度由排序和线性扫描两部分构成，即 O(N log N) + O(N)。在 Big O 表示法中，我们只保留最高阶项，因此最终的时间复杂度由排序决定，为 O(N log N)。
空间复杂度：O(log N)
- 主要存储开销：该算法在原地修改数组（通过排序），并没有创建与输入规模
N成比例的新的数据结构。 - 排序的额外空间：
- Java 的
Arrays.sort实现（双轴快速排序）是一种原地排序算法，但它需要递归。递归调用会占用调用栈（call stack）的空间。 - 对于一个性能良好的快速排序实现，递归栈的深度在平均情况下是 O(log N)，在最坏情况下可能达到 O(N)。
- Java 的
- 其他变量：
ans和i等变量只占用常数级别的空间，即 O(1)。
综合分析：
算法所需的额外辅助空间主要由排序算法的递归调用栈决定。因此，在平均情况下，其空间复杂度为 O(log N)。如果忽略排序算法内部的栈空间，可以认为是 O(1)，但 O(log N) 是一个更精确的分析。
LeetCode 热题 100】41. 缺失的第一个正数——（解法二）原地哈希
