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;
    }
};

Link

LeetCode-41 First Missing Positive