41. 缺失的第一个正数
题目描述
输入一个没有排序的整数数组 nums。
返回没有在 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 <= 10^5-2^31 <= nums[i] <= 2^31 - 1
解题思路：原地置换归位
把值 x 放到下标 x-1 的位置，反复交换直到当前位置稳定。随后第一个 nums[i] != i+1 的位置给出答案。
为什么正确
处理交换后，所有位于有效范围的已归位数字 x 都满足 nums[x-1]=x。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
交换时必须处理重复值，否则两个相同数字会导致死循环。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def firstMissingPositive(self, nums):
n=len(nums); i=0
while i<n:
x=nums[i]
if 1<=x<=n and nums[x-1]!=x: nums[i],nums[x-1]=nums[x-1],nums[i]
else: i+=1
for i,x in enumerate(nums):
if x!=i+1: return i+1
return n+1class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length, i = 0;
while (i < n) {
int x = nums[i];
if (1 <= x && x <= n && nums[x - 1] != x) { nums[i] = nums[x - 1]; nums[x - 1] = x; }
else i++;
}
for (i = 0; i < n; i++) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
}class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size(), i = 0;
while (i < n) {
int x = nums[i];
if (1 <= x && x <= n && nums[x - 1] != x) swap(nums[i], nums[x - 1]);
else i++;
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
};func firstMissingPositive(nums []int) int {
n, i := len(nums), 0
for i < n {
x := nums[i]
if 1 <= x && x <= n && nums[x-1] != x {
nums[i], nums[x-1] = nums[x-1], nums[i]
} else {
i++
}
}
for i, x := range nums {
if x != i+1 {
return i + 1
}
}
return n + 1
}var firstMissingPositive = function(nums) {
let n = nums.length, i = 0;
while (i < n) {
const x = nums[i];
if (1 <= x && x <= n && nums[x - 1] !== x) [nums[i], nums[x - 1]] = [nums[x - 1], nums[i]];
else i++;
}
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) return i + 1;
}
return n + 1;
};function firstMissingPositive(nums: number[]): number {
let n = nums.length, i = 0;
while (i < n) {
const x = nums[i];
if (1 <= x && x <= n && nums[x - 1] !== x) [nums[i], nums[x - 1]] = [nums[x - 1], nums[i]];
else i++;
}
for (let i = 0; i < n; i++) {
if (nums[i] !== i + 1) return i + 1;
}
return n + 1;
}其他解法
哈希集合最直观但占 O(n) 空间；原地负号标记和置换归位都把数组本身当作哈希表，达到 O(1) 额外空间，前者用符号做标记，后者把数放回对应位置。
解法 2：原地负号标记 时间 O(n)，空间 O(1)
答案一定在 [1, n+1] 内。先把所有非正数改成 n+1，使数组只剩正数。再遍历每个数的绝对值 x，若 x ≤ n，就把 nums[x-1] 改成负数，表示 x 出现过。最后第一个仍为正数的下标 i 给出答案 i+1，全部为负则答案是 n+1。
和置换归位一样满足 O(n) 时间、O(1) 额外空间。它用符号位充当哈希表，不需要处理交换循环，正确性更容易论证；缺点是会破坏原数组的符号。
class Solution:
def firstMissingPositive(self, nums):
n = len(nums)
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
for i in range(n):
x = abs(nums[i])
if x <= n:
nums[x - 1] = -abs(nums[x - 1])
for i in range(n):
if nums[i] > 0:
return i + 1
return n + 1class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++)
if (nums[i] <= 0) nums[i] = n + 1;
for (int i = 0; i < n; i++) {
int x = Math.abs(nums[i]);
if (x <= n) nums[x - 1] = -Math.abs(nums[x - 1]);
}
for (int i = 0; i < n; i++)
if (nums[i] > 0) return i + 1;
return n + 1;
}
}class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++)
if (nums[i] <= 0) nums[i] = n + 1;
for (int i = 0; i < n; i++) {
int x = abs(nums[i]);
if (x <= n) nums[x - 1] = -abs(nums[x - 1]);
}
for (int i = 0; i < n; i++)
if (nums[i] > 0) return i + 1;
return n + 1;
}
};func firstMissingPositive(nums []int) int {
n := len(nums)
abs := func(v int) int {
if v < 0 {
return -v
}
return v
}
for i := range nums {
if nums[i] <= 0 {
nums[i] = n + 1
}
}
for i := range nums {
x := abs(nums[i])
if x <= n {
nums[x-1] = -abs(nums[x-1])
}
}
for i := range nums {
if nums[i] > 0 {
return i + 1
}
}
return n + 1
}var firstMissingPositive = function(nums) {
const n = nums.length;
for (let i = 0; i < n; i++)
if (nums[i] <= 0) nums[i] = n + 1;
for (let i = 0; i < n; i++) {
const x = Math.abs(nums[i]);
if (x <= n) nums[x - 1] = -Math.abs(nums[x - 1]);
}
for (let i = 0; i < n; i++)
if (nums[i] > 0) return i + 1;
return n + 1;
};function firstMissingPositive(nums: number[]): number {
const n = nums.length;
for (let i = 0; i < n; i++)
if (nums[i] <= 0) nums[i] = n + 1;
for (let i = 0; i < n; i++) {
const x = Math.abs(nums[i]);
if (x <= n) nums[x - 1] = -Math.abs(nums[x - 1]);
}
for (let i = 0; i < n; i++)
if (nums[i] > 0) return i + 1;
return n + 1;
}解法 3：哈希集合 时间 O(n)，空间 O(n)
把所有数放入哈希集合。从 1 开始依次查询，第一个不在集合中的正整数就是答案。由于集合最多 n 个元素，最多查询 n+1 次。
思路最直观，但需要 O(n) 额外空间，不满足题目的常数空间要求。适合作为思路起点和对拍基准。
class Solution:
def firstMissingPositive(self, nums):
seen = set(nums)
k = 1
while k in seen:
k += 1
return kclass Solution {
public int firstMissingPositive(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int x : nums) seen.add(x);
int k = 1;
while (seen.contains(k)) k++;
return k;
}
}class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
unordered_set<int> seen(nums.begin(), nums.end());
int k = 1;
while (seen.count(k)) k++;
return k;
}
};func firstMissingPositive(nums []int) int {
seen := make(map[int]bool, len(nums))
for _, x := range nums {
seen[x] = true
}
k := 1
for seen[k] {
k++
}
return k
}var firstMissingPositive = function(nums) {
const seen = new Set(nums);
let k = 1;
while (seen.has(k)) k++;
return k;
};function firstMissingPositive(nums: number[]): number {
const seen = new Set<number>(nums);
let k = 1;
while (seen.has(k)) k++;
return k;
}