【LeetCode篇】 First Missing Positive
@(LeetCode)
- IDE: C++ (C)
- author : MinRam(minfysui@gmail.com)
- create : 03/19/2019
- update: 03/19/2019
[toc]
题目
- English: Given an unsorted integer array,find the smallest missing positive integer.
Your algorithm should run in O(n) time and uses constant extra space.
思路
大体思路，简易桶。 Num[Value -1 ] = Value
-
判断Current是否满足一下情况，若满足则2，反之3
- 正数
- 小于答案的最大值 $（所求的正数 \leq 数组长度）$
- 将Current 与Num[Current - 1] 交换。
- 下一位，重复1，直到数组遍历结束。
代码实现
class Solution {
public:
int firstMissingPositive(vector& nums) {
int numsLen = nums.size();
for (int i = 0 ; i < numsLen; ){
if (nums[i] != (i + 1) && nums[i] >= 1 && nums[i] <= numsLen && nums[nums[i] - 1] != nums[i])
swap(nums[i],nums[nums[i] - 1]);
else
++i;
}
for (int i = 0; i < numsLen; ++i)
if (nums[i] != (i + 1))
return i + 1;
return numsLen + 1;
}
}; 