【LeetCode篇】 41. First Missing Positive

【LeetCode篇】 First Missing Positive

IDE: C++ (C)
author : MinRam
create : 03/19/2019
update: 03/19/2019

题目
First Missing Positive – LeetCode

Given an unsorted integer array, find the smallest missing positive integer.
Your algorithm should run in O(n) time and uses constant extra space.

思路
大体思路，简易桶。 直接以值为Key，发散到数组中，通过Swap实现。
伪代码

判断Current是否满足一下情况，若满足则2，反之3

正数
小于答案的最大值 $（所求的正数 \leq 数组长度）$

将Current 与Num[Current – 1] 交换。
下一位，重复1，直到数组遍历结束。

图片流
代码实现
// 优化io流
static const auto __ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();

class Solution {
public:
int firstMissingPositive(vector<int>& 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;
}
};

参考
[1] Longest palindromic substring – LeetCode
反馈与建议

E-mail: minfysui@gmail.com

Q Q: MinRam