這題好像是昨天洗澡的時候想到的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; } };
好像有點像把放錯信封的信放回正確信封的感覺,這感覺很像甚麼高中排列組合的題目