力扣41. 缺失的第一个正数（Java解法）

题目描述

给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 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
解释：最小的正数1没有出现

提示：

• 1 <= nums.length <= 5 * 10^5

• -2^31 <= nums[i] <= 2^31 – 1

解题思路

这道题是「原地哈希」的经典难题，难点在于O(n)时间复杂度和常数级额外空间的双重约束-2。

关键洞察

对于一个长度为 n 的数组，缺失的第一个正数一定在 [1, n+1] 范围内-2-4。为什么？

• 如果数组包含了 1 到 n 的所有数字，那么答案就是 n+1

• 否则，答案一定是 1 到 n 中某个未出现的数字

因此，我们可以把数组本身当作哈希表来使用，将数字 i 放到下标 i-1 的位置上-9。

解法一：置换法（原地交换）【最优解】

算法思想

遍历数组，对于每个元素，如果它在 [1, n] 范围内，并且它没有在正确的位置上（即 nums[i] != i+1），就把它交换到正确的位置 nums[i]-1 上-2-9。

重复这个过程，直到当前元素要么不在范围内，要么已经在正确位置上。

代码实现

class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;

// 1. 将每个数字放到它应该在的位置
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] – 1] != nums[i]) {
// 将 nums[i] 交换到下标为 nums[i]-1 的位置
swap(nums, i, nums[i] – 1);
}
}

// 2. 遍历数组，找到第一个位置 i 上数字不是 i+1 的
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}

// 3. 如果所有位置都正确，返回 n+1
return n + 1;
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

图解示例

以 nums = [3, 4, -1, 1] 为例：

最终数组：[1, -1, 3, 4]，第一个错误的位置是下标1（应为2，实际是-1），所以返回 1+1=2 ✓

复杂度分析

• 时间复杂度： O(n)，每个元素最多被交换一次-9

• 空间复杂度： O(1)，原地修改，只使用了常数个临时变量

解法二：标记法（负数标记）

算法思想

另一种实现方式是用负数做标记-3-8：

代码实现

class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;

// 1. 将所有非正数改为 n+1（一个不会影响结果的数）
for (int i = 0; i < n; i++) {
if (nums[i] <= 0) {
nums[i] = n + 1;
}
}

// 2. 对于每个在[1,n]范围内的数，标记其对应下标位置
for (int i = 0; i < n; i++) {
int num = Math.abs(nums[i]);
if (num <= n) {
// 将下标 num-1 处的数标记为负数，表示数字num存在
nums[num – 1] = -Math.abs(nums[num – 1]);
}
}

// 3. 找到第一个正数的下标
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}

return n + 1;
}
}

图解示例

以 nums = [3, 4, -1, 1] 为例：

解法对比

代码要点详解

1. 为什么用 while 而不是 if？

在置换法中，我们使用 while 循环而不是 if，因为交换过来的新数可能仍然需要继续交换到正确位置。

// ✅ 正确写法
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] – 1] != nums[i]) {
swap(nums, i, nums[i] – 1);
}

// ❌ 错误写法 – 只能处理一次交换
if (nums[i] > 0 && nums[i] <= n && nums[nums[i] – 1] != nums[i]) {
swap(nums, i, nums[i] – 1);
}

2. 交换条件判断

交换条件 nums[nums[i] – 1] != nums[i] 是为了避免死循环-2。如果两个位置的值相等，交换没有意义，应该跳过。

3. 处理重复元素

当数组中有重复元素时，上述条件也能正确处理。例如 [2, 2]：

• i=0：nums[0]=2，下标1的值也是2，条件不成立，不交换

• 最终数组 [2, 2]，下标0应为1，所以返回1 ✓

为什么不能用除法？—— 本题不涉及

（温馨提示：本题不涉及除法，这是之前238题的考点。41题的核心是原地哈希思想。）

常见错误与注意事项

面试建议

• 优先写出置换法：这是最符合题意的标准解法，代码简洁，思路清晰-9

• 可以提及标记法：作为对比，展示你知道多种实现方式

• 解释为什么答案在[1, n+1]：展示你对问题的数学洞察-4

• 强调 while 的重要性：说明为什么不能用 if，展现你对细节的把控

相关题目推荐

• 力扣 268. 丢失的数字（原地哈希入门）

• 力扣 442. 数组中重复的数据（原地哈希应用）

• 力扣 448. 找到所有数组中消失的数字（标记法思路）

• 力扣 287. 寻找重复数（类似思想）

以上就是力扣41题"缺失的第一个正数"的Java解法详细解析，这是原地哈希思想的经典题目，重点掌握置换法这一最优解法。如果觉得文章不错，欢迎点赞、收藏、关注三连支持！