[Leetcode] 41. First Missing Positive

來挑戰 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;
    }
};