解题思路:数组没有排序,返回第一个丢掉的正整数。遍历数组,通过不断的交换,将数组排序,然后通过再次遍历,找到答案并返回。
时间复杂度:O(n) / 空间复杂度:O(1)
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for(int i = 0; i < nums.size(); ++i){
while(nums[i] > 0 && nums[i] <= nums.size() && nums[nums[i] - 1] != nums[i]){
swap(nums[nums[i] - 1], nums[i]);
}
}
for(int i = 0; i < nums.size(); ++i){
if(nums[i] != i + 1){
return i + 1;
}
}
return nums.size() + 1;
}
};