【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实现。

伪代码

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

   • 正数
   • 小于答案的最大值 $（所求的正数 \leq 数组长度）$
2. 将Current 与Num[Current - 1] 交换。
3. 下一位，重复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: [email protected]
• Q Q: MinRam