Description
Given an unsorted integer array, find the first missing positive integer.
Your algorithm should run in O(n) time and uses constant space.
Example
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.思路
- 分析一下，数组长度为len，要找第一个缺失的正数，要求O(n)和常量空间
- 调整原数组，将对应正数调到相应位置上，然后再遍历一遍，找到缺失的第一个正数
- 调整过程中注意负数、大于数组长度的情况
- 交换重复值是没有意义的
代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int len = nums.size();
if (len == 0) return 1;
int i = 0;
while (i < len){
while (i != nums[i]){
if (nums[i] < 0 || nums[i] >= len || nums[i] == nums[nums[i]])
break;
swap(nums[i], nums[nums[i]]);
}
i++;
}
for (i = 1; i < len; ++i){
if (nums[i] != i)
return i;
}
return nums[0] == len ? len + 1 : len;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
