Day 78, #41, First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
----------------------------------------------------------------

# Pass 1, move every value to the position of its value

因为找的是第一个非0，所以把1存在0,2存在1

while里的条件是检测下一个位置是否已经匹配好，如果检查当前位置的话，会进入死循环，因为会有重复的数字如[1,1]

# Pass 2, find first location where the index doesn't match the value

reference  

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for (int i = 0; i < n; i++) {
            int target = A[i];
            while (target > 0 && target <= n && A[target - 1] != target) {
                int temp = A[target - 1];
                A[target - 1] = target;
                A[i] = temp;
                target = A[i];
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (i + 1 != A[i]) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
};