【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，直到数组遍历结束。

图片流
【LeetCode篇】 41. First Missing Positive

代码实现

// 优化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;
    }
};