這題好像是昨天洗澡的時候想到的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]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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; } }; |
好像有點像把放錯信封的信放回正確信封的感覺，這感覺很像甚麼高中排列組合的題目
