Description

给定一个长度为\(n\)的数组\(a\),返回其中缺失的最小正整数。

要求时间复杂度\(O(n)\),空间复杂度\(O(1)\)。

Constraints

\(1 \le n \le 10^5\)

Solution

使用置换法,将数值\(i\)放到下标\(nums[i]\)里面,但只处理容器范围内的合法数值。

由于每次交换必能使其中一个位置正确归位,至多交换\(n\)次,因此时间复杂度是\(O(n)\)。

由于还有off-by-one问题,因此需要修正一下偏移量,使得范围统一为\([1, n]\)。

关联:287

Code

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

LeetCode-41 First Missing Positive