# 41. First Missing Positive

### Leetcode

<https://leetcode.com/problems/first-missing-positive/description/>

### 題目

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,2,0]
</strong><strong>Output: 3
</strong><strong>Explanation: The numbers in the range [1,2] are all in the array.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [3,4,-1,1]
</strong><strong>Output: 2
</strong><strong>Explanation: 1 is in the array but 2 is missing.
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [7,8,9,11,12]
</strong><strong>Output: 1
</strong><strong>Explanation: The smallest positive integer 1 is missing.
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

雖然這題有限制空間複雜度為 O(1)，但為了先理解思考的方向，我們先來看要如何用多餘的空間來計算這一題

範例：`nums = [3, 4, -1, 1, 8]`，需要回傳的結果是 `2`

1. 一開始可以先創建跟 `nums` 一樣長度的矩陣並先都設為 `-1` (`[-1, -1, -1, -1, -1]`)
2. 接著將 `nums` 中的元素按照該排的位置放入這個矩陣中

   例如：3 放到第三個元素的地方 `[-1, -1, 3, -1, -1]`
3. 如果遇到負數或是大於矩陣長度的值直接忽略就好
4. 放完後矩陣會是 `[1, -1, 3, 4, -1]`
5. 最後遍歷這個矩陣找出 `arr[i] !== i+1` 的元素時，`i+1` 的 2 就是答案了

但上面的方式空間複雜度是 O(n)，如果要達到 O(1) 的話勢必要用原本的矩陣進行交換，下面我們來看看如何用同一個矩陣達到上面一樣的效果

1. 一樣我們先從頭把元素放到該放的地方，第一步會先將 `3` 與第三個位置的元素交換

   結果是： `[-1, 4, 3, 1, 8]`&#x20;
2. 接著看交換回來的 `-1` 由於是負數所以暫時不用處理
3. 接著第二個元素 `4` 需要與第四個元素 `1` 交換

   結果是： `[-1, 1, 3, 4, 8]`
4. 交換回來的 `1` ，因為是正整數，所以需要再把他排到該放的位置，即與第一個元素交換

   結果是： `[1, -1, 3, 4, 8]`
5. 交換回來的 `-1` 由於是負數，可以不用處理
6. 最後一個元素 `8` 因為超過了整個矩陣的長度，所以也不用處理

最後會發現這樣就是我們上面想做到的結果了

```javascript
var firstMissingPositive = function (nums) {
    const swap = (i, j) => {
        const temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    for (let i = 0; i < nums.length; i++) {
        let value = nums[i];
        // 判斷三個條件
        // 1. 元素是正整數
        // 2. 元素小於矩陣總長度
        // 3. 交換前後元素要不一樣，避免無限迴圈 (ex. [1, 1])
        while (value > 0 && value <= nums.length && value !== nums[value - 1]) {
            swap(i, value - 1);
            value = nums[i];
        }
    }

    for (let i = 0; i < nums.length; i++) {
        // 如果 match 不到，i+1 就是缺少的最小正整數
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }

    return nums.length + 1;
};
```

Runtime: 55 ms Beats 98.11% of users with JavaScript

Memory: 55.67 MB Beats 72.69% of users with JavaScript

**參考資料**

{% embed url="<https://leetcode.wang/leetCode-41-First-Missing-Positive.html>" %}
