runtime 48 ms, beats 93.89% of cpp submissions
O(n) solution with explanation

tags: none

First Missing Positive

📖 description

給定一個陣列 nums ，求出第一個不在 nums 裡的正數 (從 1 開始)
要求時間複雜度 O(n) ，空間複雜度 O(1)

ex.
    Input: nums = [1,2,0]

    Output: 3

    Explanation: 
        The numbers in the range [1,2] are all in the array.

🧠 solution

本題是一個連暴力解都比較難想的題目，但只要掌握一個關鍵，題目就變得很簡單了。
要求出第一個不在陣列中的正數，假設這個數字是 k ，那我們要做的事就是維護前 k-1 個正數，看他們是否都是存在的，所以只需要使用一個最多 n 長的陣列 ( n 為 nums 長度) ，將 nums 的元素 map 進陣列中，再掃過一次就知道答案了，但因為題目要求不能使用額外空 間，所以我們可以使用 nums 來替代儲存空間。

主要得做法如下

ex.
    Input: nums = [3,4,-1,1]
    Output: 2
                        
    將數字 map 到陣列中後，我們可以建構出這樣的結果

     1   2  3  4
    [1, -1, 3, 4]
    
    我們可以發現只有 index 為 2 的部分是我們找不到的，所以答案就是 2

⏳ time complexity

掃過陣列並 map 回去，時間複雜度為 O(n)
再掃過一次陣列確認答案，時間複雜度為 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        while(i<n){

            // 交換元素。直到元素正確排列
            if(nums[i]>0 && nums[i]<=n && nums[i]!=nums[nums[i]-1]){
                swap(nums[i],nums[nums[i]-1]);
            }
            else{
                // 當前元素正確排列了，看下一個
                i++;
            }
        }
        // 掃過一次陣列並回傳答案
        for(int j = 0;j<n;j++){
            if(nums[j]!=j+1){
                return j+1;
            }
        }
        // 如果陣列中的元素都沒有缺失
        return n+1;
    }
};