Leetcode 41. 缺失的第一个正数

(Updated: )
(2 mins to read)

题意

给定一个长度为$n$的数组$a$，对其中的所有正数求mex。要求时间复杂度$O(n)$，额外空间复杂度$O(1)$。

做法

排序，时间复杂度不行。

桶排序，空间复杂度不行。

显然只能对$a$数组本身进行原地的操作 (in place)，最后希望能根据$a[i]$的取值判断出$i$是否存在于原数组中。

那就按下标顺序从小到大依次标记。设当前下标为$i$，如果$a[i]\gt i$，就先标记$a[a[i]]$，然后再覆盖$a[a[i]]$处的值来标记$a[i]$的存在；而如果$a[i]\le i$，直接对$a[a[i]]$进行标记即可。

下一个难点是用什么值来标记。显然可以取不在原数组中的任意值，但是$O(n)$算不出来，而原数组的取值范围又是整个int区间，不能用max+1，min-1这个trick。我的做法就是用n+1来标记，但需要把原数组中的n+1都先改成n+2（一开始没意识到要改，wa了一次），因为可以知道答案一定是小于等于n+1的，所以大于等于n+1的数的取值是无所谓的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        nums.push_back(0);
        for (int &x : nums) if (x == n + 1) x = n + 2;
        for (int i = 0; i < n; i++) {
            int j = i, x = nums[j];
            while (x > i && x <= n) {
                int tmp = nums[x];
                nums[x] = n + 1;
                x = tmp;
            }
            if (x >= 0 && x <= i) nums[x] = n + 1;
        }
        int d = 1;
        while (d <= n && nums[d] == n + 1) ++d;
        return d;
    }
};

看了题解才意识到这是置换的做法。

此外还有一种正负的做法（或者称为哈希）：显然负数是没用的，所以可以用负号作为标记的手段，与此同时绝对值保留为原取值，这样都不用担心覆盖的问题，不需要进行置换，更好写了。本质有点类似压位，反正就是在一个int的32bit里表达更多的信息。