【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