题目描述: 给定一系列为排序的整数, 求出最小的缺失的正数.
题解: 对于给定的 N 个数, 对于小于等于 0 以及大于 N 的数字不予处理, 其余的数字在一次遍历的时候将其放在对应的位置上. 例如给定 < 1,3,-1,4>,1 的位置不用变, 3 与 - 1 交换, 4 不用变. 处理之后检查一下 index 上的数字是否对应, 不对应的数字就是缺失那个正数.
代码:
- int firstMissingPositive(vector<int>& nums) {
- int Len = nums.size();
- int pos = 0;
- for(int i=0;i<Len;i++)
- {
- while(nums[i]> 0 && nums[i] <= Len && nums[nums[i]-1] != nums[i])
- {
- int tmp_pos = nums[i]-1;
- int tmp = nums[tmp_pos];
- nums[tmp_pos] = nums[i];
- nums[i] = tmp;
- }
- while(pos < Len && nums[pos] == pos+1) pos++;
- }
- return pos+1;
- }
来源: http://www.bubuko.com/infodetail-3362799.html