# 41. 缺失的第一个正数

# 题目描述

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

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

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

1
2
3

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

1
2
3

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

1
2
3

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

# 思路

暴力解法是从1开始遍历，逐个检查是否在数组中，时间复杂度O(n²)或者用哈希表O(n)但空间O(n)。

题目要求时间O(n)，空间O(1)，这就很有挑战性了。

核心思路：把数组本身当作哈希表，利用下标和值的对应关系。

关键观察：

数组长度为 n，那么缺失的第一个正整数一定在 [1, n+1] 范围内
如果 [1, n] 都出现了，答案就是 n+1；否则答案在 [1, n] 中

原地哈希的思路：

让数字 i 出现在下标 i-1 的位置（因为数组下标从0开始）
比如 1 应该在 nums[0]，2 应该在 nums[1]，以此类推

具体步骤：

遍历数组，将每个数字放到它应该在的位置
- 对于 nums[i]，如果 1 ≤ nums[i] ≤ n，就把它放到 nums[nums[i]-1]
- 用交换实现，不断交换直到当前位置的数字无法再交换
再次遍历数组，找第一个 nums[i] != i+1 的位置
- 这个位置的下标 i，对应的应该是数字 i+1
- 如果 nums[i] != i+1，说明 i+1 缺失
如果都满足 nums[i] == i+1，说明 [1, n] 都出现了，答案是 n+1

注意点：

交换时要避免死循环：只有当 nums[i] 和 nums[nums[i]-1] 不同时才交换
超出范围的数字（≤0 或 >n）不管它们

# 模拟过程

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

初始： [3, 4, -1, 1]

i=0，nums[0]=3：

3 应该在下标 2（即 nums[2]）
交换 nums[0] 和 nums[2]：[-1, 4, 3, 1]
现在 nums[0]=-1，超出范围，停止

i=1，nums[1]=4：

4 应该在下标 3（即 nums[3]）
交换 nums[1] 和 nums[3]：[-1, 1, 3, 4]
现在 nums[1]=1，应该在下标 0
交换 nums[1] 和 nums[0]：[1, -1, 3, 4]
现在 nums[1]=-1，超出范围，停止

i=2，nums[2]=3： 3 在正确位置，跳过

i=3，nums[3]=4： 4 在正确位置，跳过

调整完成： [1, -1, 3, 4]

找缺失：

nums[0]=1，正确
nums[1]=-1 ≠ 2，缺失 2
返回 2

# 解题代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        
        // 第一步：将每个数字放到它应该在的位置
        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[nums[i] - 1]);
            }
        }
        
        // 第二步：找第一个 nums[i] != i+1 的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1; // 缺失的正整数
            }
        }
        
        // 第三步：如果 [1, n] 都在，答案是 n+1
        return n + 1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 复杂度分析

时间复杂度：O(n)，每个元素最多交换一次到正确位置
空间复杂度：O(1)，原地修改数组

# 其他语言

# Python3

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 第一步：将每个数字放到它应该在的位置
        for i in range(n):
            while 0 < nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                # 交换 nums[i] 到它应该在的位置
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        
        # 第二步：找第一个 nums[i] != i+1 的位置
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        
        # 第三步：如果 [1, n] 都在，答案是 n+1
        return n + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Java

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]) {
                // 交换
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        
        // 第二步：找第一个 nums[i] != i+1 的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        // 第三步：如果 [1, n] 都在，答案是 n+1
        return n + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Go

func firstMissingPositive(nums []int) int {
    n := len(nums)
    
    // 第一步：将每个数字放到它应该在的位置
    for i := 0; i < n; i++ {
        for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    
    // 第二步：找第一个 nums[i] != i+1 的位置
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }
    
    // 第三步：如果 [1, n] 都在，答案是 n+1
    return n + 1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# JavaScript

var firstMissingPositive = function(nums) {
    const n = nums.length;
    
    // 第一步：将每个数字放到它应该在的位置
    for (let i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            // 交换
            [nums[i], nums[nums[i] - 1]] = [nums[nums[i] - 1], nums[i]];
        }
    }
    
    // 第二步：找第一个 nums[i] != i+1 的位置
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    
    // 第三步：如果 [1, n] 都在，答案是 n+1
    return n + 1;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 与代码随想录联系

本题是哈希表思想的进阶应用——原地哈希。

在代码随想录的哈希表章节中，讲解了：

什么时候用数组作为哈希表
什么时候用 set
什么时候用 map

本题的关键：把数组本身当作哈希表，下标就是 key，值就是 value。

这种技巧在空间受限的场景下非常有用，但需要注意：

下标和值的映射关系要设计好
交换时要避免死循环（判断 nums[i] != nums[nums[i]-1]）
超出范围的值要跳过

类似的原地哈希题目还有：

如果录友们对哈希表还不熟悉，建议先学习代码随想录哈希表章节，理解哈希表的基本用法后，再来学习原地哈希会更容易。

验证登录状态...

# 41. 缺失的第一个正数

# 题目描述

# 思路

# 模拟过程

# 解题代码

# 复杂度分析

# 其他语言

# Python3

# Java

# Go

# JavaScript

# 与代码随想录联系

评论