41. 缺失的第一个正数

二哥瞎逼逼：人生最大的牢笼其实都是自己给的，以前我觉得刷 LeetCode 没多

大用，也不需要，最近写 LeetCode 刷题笔记，反而得到了一些以前不曾有的快

乐，尤其是对代码的一些逻辑推敲，感觉更清晰了。

题意

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

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

难度

困难

示例

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

输出：3

解释：范围 [1,2] 中的数字都在数组中。

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

输出：2

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

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

输出：1

解释：最小的正数 1 没有出现。

分析 1

我们先不考虑“时间复杂度为 O(n) 并且只使用常数级别额外空间”这个限制条件。

好，先搞清楚正数是什么？

正数是大于 0 的整数，那么我们可以直接暴力来解题。

• 获取数组的长度 n。

• 从 1 开始检查每个正整数是否存在于数组中，直到找到第一个不存在的正整数。

• 使用双重循环，外层循环遍历正整数 i，内层循环遍历数组 nums，检查 i 是否存在于

数组中。

• 如果当前整数 i 不存在于数组中，返回 i。

也就是说，假如输入是 [1, 2, 0]，那么我们就从 1 开始检查，1 存在于数组中，2 也存在

于数组中，3 不存在于数组中，所以返回 3。

假如输入是 [3, 4, -1, 1]，还是从 1 开始检查，1 ≠ 3,1≠4，1≠-1，1=1，好，1 存在于数组

中，然后开始检查 2，很显然，2 不存在于数组中，所以返回 2。

class Solution {

public int firstMissingPositive(int[] nums) {

int n = nums.length;

// 从 1 开始检查每个正整数是否存在于数组中

for (int i = 1; i <= n + 1; i++) {

boolean found = false;

for (int j = 0; j < n; j++) {

if (nums[j] == i) {

found = true;

break;

}

}

// 如果当前整数 i 不存在于数组中，返回 i

if (!found) {

return i;

}

}

// 理论上不会执行到这里，因为我们在 for 循环中返回了结果

return n + 1;

}

public static void main(String[] args) {

Solution solution = new Solution();

int[] nums1 = {1, 2, 0};

int[] nums2 = {3, 4, -1, 1};

int[] nums3 = {7, 8, 9, 11, 12};

System.out.println("缺失的第一个正数: " +

solution.firstMissingPositive(nums1)); // 输出 3

System.out.println("缺失的第一个正数: " +

solution.firstMissingPositive(nums2)); // 输出 2

System.out.println("缺失的第一个正数: " +

solution.firstMissingPositive(nums3)); // 输出 1

}

}

但是很遗憾，这种解法不符合要求，虽然很好理解。

041.缺失的第一个整数-20240806153725.png

分析 2

解决这个问题的一种有效方法是利用数组本身作为哈希表来标记出现的正数。我们可以将

每个数放到它对应的索引位置上（即 1 放在 nums[0]，2 放在 nums[1] 以此类推）。最

后，我们再遍历一次数组，第一个不满足条件的位置就是缺失的最小正整数。

大致的思路如下：

1. 遍历数组，如果 nums[i] 是正数且在范围内（即 1 到 n），并且不在正确的位置上

（即 nums[i] != nums[nums[i] - 1]），则交换它和它正确位置上的数。

2. 遍历数组，第一个位置 i，使得 nums[i] != i + 1，则 i + 1 就是缺失的最小正整数。

假如输入是 [3, 4, -1, 1]，我们可以模拟整个交换过程：

041.缺失的第一个整数-20240806161333.png

交换后的结果是 [1, -1, 3, 4]，然后我们遍历数组。

for (int i = 0; i < n; i++) {

if (nums[i] != i + 1) {

return i + 1;

}

}

• i = 0，nums[0] = 1，i + 1 = 1。

• i = 1，nums[1] = -1，i + 1 = 2。

发现 nums[i] != i + 1，返回 2。好，来看整个题解过程。

class Solution {

public int firstMissingPositive(int[] nums) {

int n = nums.length;

// 将每个数放到正确的位置上

 for (int i = 0; i < n; i++) {

while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {

// 交换 nums[i] 和 nums[nums[i] - 1]

int temp = nums[nums[i] - 1];

nums[nums[i] - 1] = nums[i];

nums[i] = temp;

}

}

// 寻找第一个不满足条件的位置

for (int i = 0; i < n; i++) {

if (nums[i] != i + 1) {

return i + 1;

}

}

// 如果所有位置都满足条件，则返回 n + 1

return n + 1;

}

public static void main(String[] args) {

Solution solution = new Solution();

int[] nums1 = {1, 2, 0};

int[] nums2 = {3, 4, -1, 1};

int[] nums3 = {7, 8, 9, 11, 12};

System.out.println("缺失的第一个正数: " +

solution.firstMissingPositive(nums1)); // 输出 3

System.out.println("缺失的第一个正数: " +

solution.firstMissingPositive(nums2)); // 输出 2

System.out.println("缺失的第一个正数: " +

solution.firstMissingPositive(nums3)); // 输出 1

}

}

直接击败了 100% 的选手，效率非常高。

041.缺失的第一个整数-20240806161825.png

这个题解的关键就在于 nums[nums[i] - 1] != nums[i]，巧妙之处在于它确保了数组中的

每个正整数被放置在其正确的位置上。如果一个数 x 在数组中，它应该被放在索引 x - 1

的位置上。

也就是说 2 应该出现在 2-1 的位置上，3 应该出现在 3-1 的位置上，以此类推。假如有一

个不满足，那么就是缺失的最小正整数。

比如说输入是 [7, 8, 9, 11, 12]，显然 1 没有出现在 1-1 的位置上。

总结

这道题看似是一道 hard，但其实考察的内容无外乎 for 和 while 循环，当我们需要交换数

组中的元素时，记得使用 temp 变量临时保存一下。

int temp = nums[nums[i] - 1];

nums[nums[i] - 1] = nums[i];

nums[i] = temp;

力扣链接：https://leetcode.cn/problems/first-missing-positive/