[LeetCode] First Missing Positive

這題好像是昨天洗澡的時候想到的XD

https://leetcode.com/problems/first-missing-positive/description/

洗澡的時候思緒真的比較豐富阿，有時候覺得coding跟寫作沒兩樣阿，都是需要靈感的XDD

一開始沒啥靈感，看了hint去洗澡想了想hint在講三小，然後就想到喔喔直接開一個一樣大小的array然後mapping過去就好了啊

然後再看一下哪一格是空的就好了，但題目說要constant space，hint更直接了要你用existing space

想想好像沒什麼招數啊啊，在原有的空間上….阿不就一直swap

一開始以為是單純swap就好，但這樣loop完一定會有幾個subset自己形成一個小圈圈，像是下面2,3又是自閉的小群組QQ

[5,4,1,3,2] => [2,4,1,3,5] => [2,3,1,4,5] =>[1,3,2,4,5]

所以一開始位置就要放對的數字，不然等等iterator過頭就沒什麼機會救了，除非運氣好又換到

剛剛上述的case，a[0]目標就是放1，所以就一直swap，順便把錯的數字往後面正確的位置送，應該是這樣(?)

[5,4,1,3,2] => [2,4,1,3,5] => [4,2,1,3,5] => [3,2,1,4,5] => [1,2,3,4,5]

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

好像有點像把放錯信封的信放回正確信封的感覺，這感覺很像甚麼高中排列組合的題目