Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

給定一個為排序的整數陣列 nums，回傳陣列nums中沒有出現的最小正整數。
你必須實現的演算法，該算法的時間複雜度為 O(n)，並且使用 O(1) 的輔助空間。

[註]「使用 O(1) 的輔助空間」的意思就是不能使用額外的陣列或list來儲存資料。

解題思路
先來看題目，從題目提供的範例可以觀察到以下幾點:

1. 陣列中可能存在 負整數 以及 重覆的正整數，因為題目要求要回傳 不存在的最小正整數，所以這兩種狀況可以忽略不計，我們只需檢查正整數的部份，去找到不存在的最小正整數即可。
2. 如果陣列中所有的元素都是正整數，且排序後每個元素都有對應的索引值，則最小正整數為 陣列最大索引值 + 1。如Example 1，因為陣列nums中所有的正整數從0開始排序，所以那個不存在的最小正整數並不在陣列中，所以最小正整數為3。

總結來說，只要在陣列中把每個正整數放到對應的索引位置，也就是利用Cyclic Sort(循環排序)，例如:正整數6就放到索引值5的位置(請注意正整數值與索引值之間對應的關係，索引值 = 正整數值 - 1)，然後比對陣列中每個索引值對應的正整數值是否正確，若不正確，表示找到了不存在的正整數，並回傳該索引值。

步驟

1. 使用for loop排序陣列nums裡面所有的正整數
   • 當 該整數大於0(表示是我們要找的正整數) 且 該整數值在陣列長度內(表示不超出可排列的範圍) 且 該整數值與當前索引值不同時，進行交換(表示不在對的位置上)
2. 使用for loop檢查陣列nums裡面有沒有不存在的正整數
   • 若當前正整數與索引值應該對應的正整數 數值不同，則回傳索引值應該對應的正整數(表示這就是the missing number(不存在的數字))
3. 如果for loop都跑完沒有找到the missing number(不存在的數字)，表示最小的正整數在陣列外

程式碼

var firstMissingPositive = function(nums) {
    const n = nums.length;

    // 將每個數字放到正確的位置上
    for (let i = 0; i < n; ++i) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            // 交換nums[i]和它應該在的正確位置上的值
            let correctIndex = nums[i] - 1;
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        }
    }

    // 找到第一個和對應索引值不同的正整數
    for (let i = 0; i < n; ++i) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }

    // 如果陣列中所有的正整數都在正確的位置上，回傳 n+1
    return n + 1;
};