LeetCode. First Missing Positive 解析(思維)

今天我們來看看LeetCode. First Missing Positive 題目連結

題目描述

給定一個未排序的整數數組 nums，找出其中最小的缺失正整數。

性能要求

• 時間複雜度：$O(n)$
• 額外空間：常數級，即 $O(1)$

資料範圍

• 整數數組 nums 的長度範圍：
  $$1 \le \text{nums.length} \le 10^5$$

• 每個元素的取值範圍（32位有符號整數）：
  $$-2^{31} \le \text{nums}[i] \le 2^{31} – 1$$

前言

這題Hard蠻有趣的

想法

這題顯然可以用$O(n\lg n)$的sort來直接解決，但是題目要求要$O(n)$，而且空間還不能另外開。
其實只要想到一個想法，基本上就離解出來不遠了。
注意到我們可能輸出的答案是$[1,2,…,\text{nums.size()}]$，所以當你碰到不在這個範圍裡的數字，就可以都先設成0。
如果遇到在這個範圍的數字呢？可以想到，如果我們能夠把數字$x$放到$\text{nums}[x-1]$，這樣最後我們只要再遍歷一次array就可以找到哪一個最小的正整數沒出現過了。
但是當你實際開始做這件事的時候會有一個問題，如果$\text{nums}[x-1]$也包含了一個正確範圍的數字怎麼辦？我們必須先把這個數字放到好的位置才行，否則我們就會覆蓋掉一個好的數字。
於是我們可以遞迴地做這件事，直到我們放的位置就是當前位置，或者遇到不在我們考慮範圍的數字時就會停止。
只是要稍微考慮一下一個狀況：我們遇到數字$\text{nums}[i] = x$，要把它放到$\text{nums}[x-1]$，結果又經過幾輪遞迴以後，又要把某個數字放回到$\text{nums}[i]$怎麼辦？我們的程式會看到一個合法的數字，又繼續遞迴下去。
因此我們需要先設定$\text{nums}[i] = 0$再遞迴下去，以終止這個dead lock。(當然，原始的數字$x$先用一個變數存起來)
至於可能會擔心這樣遞迴下去複雜度會超越$O(n)$。可以這樣想，每一次遞迴，假設遞迴了$k$層，那麼就有$k$個index被設定為正確的數字或者$0$。之後的遞迴只要遇到這些數字都會直接停止，因此可以發現，這種遞迴的行為最多$2n$次，是$O(n)$的。

程式碼:

class Solution {
public:
    void putNumber(vector<int>& nums, int idx){
        if(nums[idx]<=0 or nums[idx]>nums.size()){
            nums[idx] = 0;
            return;
        }
        if(nums[idx] == idx + 1) return;
        if(nums[nums[idx] - 1] <= 0 or nums[nums[idx] - 1] > nums.size()){
            nums[nums[idx] - 1] = nums[idx];
            nums[idx] = 0;
        }else{
            int curNum = nums[idx];
            nums[idx] = 0;
            putNumber(nums, curNum - 1);
            nums[curNum - 1] = curNum;
        }
    }
    int firstMissingPositive(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            if(nums[i]<=0 or nums[i]>nums.size()){
                nums[i] = 0;
                continue;
            }else if(nums[i] == i + 1){
                continue;
            }else{
                putNumber(nums, i);
            }
        }
        int ans = 1;
        for(int i=0;i<nums.size();i++){
            if(nums[i] == ans) ans++;
        }
        return ans;
    }
};