LeetCode 41. First Missing Positive

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n = nums.size();
        for (int i = 0; i < n; ++i)
            if (nums[i] <= 0)
                nums[i] = n + 1; // makes all nums as positive integer.
        for (int i = 0; i < n; ++i) {
            int num = abs(nums[i]);
            if (num <= n)
                nums[num - 1] = -abs(nums[num - 1]); // taged as negative integer.
        }
        for (int i = 0; i < n; ++i)
            if (nums[i] > 0) // have not been taged, indicating the num missed.
                return i + 1;
        return n + 1; // [1..n] all taged, the ans should be "n + 1". 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n = nums.size();
        for (int i = 0; i < n; ++i)
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
                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;
    }
};

Reference: Java/C++ O(N) solution using cyclic swapping - LeetCode Discuss.