缺失的第一个正数

题意

未排序整数数组，找出其中没有出现的最小的正整数。要求 O(n) 时间、O(1) 额外空间。

思路

排序 O(n log n) 不够快。核心观察：答案一定在 [1, n+1] 范围内。把值 x 放到下标 x-1 的位置（类似原地哈希），然后扫描第一个下标和值不匹配的位置。

只关注 [1, n] 的值，超出范围的不管。
用 swap 循环放置，每个值至多被交换一次。

代码

cpp

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
26
27
28
29
30
31
32
33/**
 * Author by Rainboy
 */
// main.cpp：把值 x 放到下标 x-1，第一个 a[i] != i+1 即答案，O(n)。
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int> &nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                swap(nums[i], nums[nums[i] - 1]);
        }
        for (int i = 0; i < n; i++)
            if (nums[i] != i + 1)
                return i + 1;
        return n + 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().firstMissingPositive(a) << '\n';
    return 0;
}

python

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#!/usr/bin/env python3
from typing import List


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                x = nums[i] - 1
                nums[i], nums[x] = nums[x], nums[i]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1


def main() -> None:
    n = int(input())
    nums = list(map(int, input().split()))
    print(Solution().firstMissingPositive(nums))


if __name__ == "__main__":
    main()

复杂度

时间复杂度：O(n)，每个元素至多被交换一次。
空间复杂度：O(1)，原地交换。

总结

"值域与下标映射"是 O(1) 空间哈希的常用手法。利用出题范围 [1, n] 把数组本身当作哈希表。

缺失的第一个正数

目录

题意

思路

代码

复杂度

总结