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