https://www.cnblogs.com/grandyang/p/4395963.html
https://www.jianshu.com/p/cf82ce91dc3d
错误解法1:
[1,1]的时候会死循环
这种写法,错误在nums[i] != i+1,这种写法不能解决出现两个相同数字的情况。nums[nums[i] - 1] != nums[i]的写法能解决如果index那个位置已经放好了满足要求的数,就可以退出循环。
class Solution { public: int firstMissingPositive(vector<int>& nums) { for(int i = 0;i < nums.size();i++){ while(nums[i] != i+1 && nums[i] <= nums.size() && nums[i] > 0) swap(nums[i],nums[nums[i] - 1]); } for(int i = 0;i < nums.size();i++){ if(nums[i] != i + 1) return i + 1; } return nums.size() + 1; } };
错误解法2:
{3,4,-1,1}会错误
swap要一直循环。
class Solution { public: int firstMissingPositive(vector<int>& nums) { for(int i = 0;i < nums.size();i++){ if(nums[i] <= nums.size() && nums[i] > 0 && nums[nums[i] - 1] != nums[i]) swap(nums[i],nums[nums[i] - 1]); } for(int i = 0;i < nums.size();i++){ if(nums[i] != i + 1) return i + 1; } return nums.size() + 1; } };
正确解法:
class Solution { public: int firstMissingPositive(vector<int>& nums) { for(int i = 0;i < nums.size();i++){ while(nums[i] <= nums.size() && nums[i] > 0 && nums[nums[i] - 1] != nums[i]) swap(nums[i],nums[nums[i] - 1]); } for(int i = 0;i < nums.size();i++){ if(nums[i] != i + 1) return i + 1; } return nums.size() + 1; } };
leetcode 41. First Missing Positive
原文:https://www.cnblogs.com/ymjyqsx/p/10908518.html