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.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

解答

• 方法一

雖然這題有限制空間複雜度為 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]

2. 接著看交換回來的 -1 由於是負數所以暫時不用處理

3. 接著第二個元素 4 需要與第四個元素 1 交換

   結果是： [-1, 1, 3, 4, 8]

4. 交換回來的 1 ，因為是正整數，所以需要再把他排到該放的位置，即與第一個元素交換

   結果是： [1, -1, 3, 4, 8]

5. 交換回來的 -1 由於是負數，可以不用處理

6. 最後一個元素 8 因為超過了整個矩陣的長度，所以也不用處理

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

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

參考資料

41. First Missing Positive · leetcodeleetcode.wang