# 41. First Missing Positive

## 題目概要

給定一個未排序的整數陣列nums，返回缺失的最小正整數。

時間複雜度必須是 `O(n)`。

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

## 解題技巧

- 因為負數在這題中沒有任何意義所以要篩掉，接著將陣列由小到大排序。
- 如果 nums 長度為 0 或者 `nums[0]` 不為 1 時就返回`1`。
- 如果 nums 長度大於 0 且 `nums[0] === 1`，就代表缺失的正整數會在中間或者最後，我們可以用一個 for 迴圈遍歷 0 ~ nums.length，相鄰兩數兩兩比較，如果差值大於 1 就代表中間有兩數之間有缺失的數，返回該數即可。

## 程式碼

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    nums = nums.filter(item => item > 0); // 去掉負數

    if (nums.length) {
        nums.sort((a, b) => a - b); // 排序

        if (nums[0] !== 1) {
            // 如果沒有 1 就回傳 1
            return 1;
        } else {
            // 兩兩比較相差是否為 1, 如果不是就返回 nums[i] + 1
            for(let i = 0; i < nums.length - 1; i++) {
                if (nums[i + 1] - nums[i] > 1) {
                    return nums[i] + 1;
                }
            }
            // 否則回傳最後一個數 + 1
            return nums.pop() + 1;
        }
    } else return 1;
};