Description

Submission

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

References

1. https://leetcode.com/problems/first-missing-positive/discuss/735695/Java-Time-O(n)-Constant-space-SWAP-approach