【LeetCode篇】 41. First Missing Positive

【LeetCode篇】 First Missing PositiveIDE: C++ (C)author : MinRamcreate : 03/19/2019update: 03/19/2019题目First Missing Positive - LeetCodeGiven 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.comQ Q: MinRam