41. 缺失的第一个正整数
1. 题目简介
难度：困难，原题链接：41. 缺失的第一个正整数。
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
2. 问题分析
虽然题目的描述很简单，但是本题的难度却是「困难」，难点都集中在第二句的限制上，毕竟不加限制的话可以通过排序加遍历轻松解决，充其量是一个「简单」难度的题目。
让我们仔细分析一下题目的要求。数组的长度为 n，那么第一个缺失的正数存在三种情况：
- 数组中恰好包含
1到n的所有整数，那么缺失的第一个正整数为n + 1。 - 数组中包含了至少一个不属于
[1, n]中的数字 - 数组中包含了
[1, n]中数字，但是存在重复的数字
考虑一种理想的情况，如果数组中恰好包含 1 到 n 中所有整数，且所有的数组按照顺序排列，那么对于任意 i ∈ [1, n]，它在数组中的位置为 i - 1，即 nums[i - 1] = i。我们称这样的数字 i 处在「理想位置」上。也就是说，如果我们能将数组 nums 中所有在 [1, n] 的数字都放在理想位置上，那么第一个不满足 nums[i - 1] = i 的位置就是缺失的第一个正整数。如果全部处于理想位置上，那么缺失的第一个正整数就是 n + 1。
我们可以遍历原始数组，在遍历的过程中，如果当前元素 nums[i] 满足 1 <= nums[i] <= n，那么将其交换到 nums[nums[i] - 1] 的位置上。需要额外考虑的一种情况是，如果元素 nums[i] 出现重复，且在其理想位置上已经放置了一个同样的 nums[i]，那么此时不需要交换，避免死循环。
3. 代码实现
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 第一次遍历：将数字放到理想位置
for (int i = 0; i < n; i++) {
// 当前数字在 1~n 之间且不在理想位置时进行交换
while (nums[i] != i + 1 && nums[i] > 0 && nums[i] <= n) {
int swap = nums[i];
// 避免重复数字导致的死循环
if (nums[swap - 1] == swap) {
break;
}
nums[i] = nums[swap - 1];
nums[swap - 1] = swap;
}
}
// 第二次遍历：找到第一个不在理想位置的数字
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
4. 复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
我们对原数组遍历了两次，第一次遍历将所有在 [1, n] 的数字交换到理想位置上，第二次遍历找到第一个不满足 nums[i - 1] = i 的位置。此时的时间复杂度为 O(n)。
空间上，只使 用了常数级别的空间用来交换元素位置，因此空间复杂度为 O(1)。
5. 其他
这道题可能是我印象最深的几道面试题之一。因为这是我在面试微软时遇到的原题，甚至在五轮面试中被两个面试官分别问了这道题。
希望大家也能在面试过程中遇到原题～