來挑戰 Hard 拉,參考了一下大神講解,思路其實不難,不過難的是要怎麼想到。

這題最重要的概念應該就是要物歸原位(誤。

例如 [3,4,-1,1],其實應該要排成 [1,-1,3,4],這樣就可以看出 -1 這格應該要是 2

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if(nums.empty()) return 1;
        for(int i=0; i< nums.size();){
            if((nums[i]>0) && (nums[i]<nums.size()) && (nums[i] != i+1)){
                if(nums[i] == nums[nums[i]-1]) {
                    i++;
                    continue;
                }
                int tmp = nums[i];
                nums[i] = nums[nums[i]-1];
                nums[tmp-1] = tmp;
            }
            else {
                i++;
            }
        }
        for(int i=0; i<nums.size(); i++)
            if(nums[i] != i+1)
                return i+1;
        
        return nums.size()+1;
    }
};

整理一下扣,i++ 判斷的地方可以改成 while,當換到滿足條件後直接下一 run,如此一來 code 也簡潔了不少

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if(nums.empty()) return 1;
        for(int i=0; i< nums.size(); i++){
            while((nums[i]>0) && (nums[i]<nums.size()) && (nums[nums[i]-1] != nums[i])){
                int tmp = nums[i];
                nums[i] = nums[nums[i]-1];
                nums[tmp-1] = tmp;
            }
        }
        for(int i=0; i<nums.size(); i++)
            if(nums[i] != i+1)
                return i+1;
        
        return nums.size()+1;
    }
};

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料