leetcode 41: First Missing Positive

這次的題目是找出給定陣列中，缺少的最小正整數 像是 [1, 3, 0] 就是 2 ， [3, 5, -1, 4] 就是 1 ， 答案一定是從 1 開始找 最直接的做法就是，從 1 開始依序尋找是否出現在陣列中，這作法複雜度是 $O(n^2)$ ， 然而題目有要求解答需要是 $O(n)$ 的 其實觀察後可以發現，假設每個數字都有出現的話，整個陣列 arr 裡面的內容必定是 1~n 也就是說，當我們把 i 放在 arr[i-1] 時，只要找到最小的不符合 arr[i-1] == i 的數字，就是我們所求的答案 而這種作法也只需遍歷陣列兩次，所以複雜度為 $O(n)$ 比較需要注意的是，中間的條件判斷要考慮多種情況

void swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

// put i in nums[i-1], find first number doesn't satisfy nums[i]==i+1
int firstMissingPositive(int* nums, int numsSize)
{
    for(int i=0 ; i<numsSize ; i++)
        while(nums[i] != i+1 && // at right position
              nums[i] <= numsSize && // out of range
              nums[i] > 0 && // out of range
              nums[i] != nums[nums[i]-1]) // avoid infinite loop
            swap(&nums[i], &nums[nums[i]-1]);

    for(int i=0 ; i<numsSize ; i++)
        if(nums[i] != i+1) return i+1;

    return numsSize + 1;
}