【LeetCode篇】 41. First Missing Positive_C++教程

上一篇: PHP中的符号 ->、=> 和 :: 分别表... 下一篇:你无法忍受Google Test的9个特性

【LeetCode篇】 41. First Missing Positive

发布时间：2019-08-06 发布网站：脚本宝典

脚本宝典收集整理的这篇文章主要介绍了【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，直到数组遍历结束。

图片流

代码实现

      
      
      PE="button" class="copyCode code-tool" data-toggle="tooltip" data-placement="top" data-clipboard-text="// 优化io流
static const auto __ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int firstMissingPositive(vector&amp; 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;
    }
};" title="" data-original-title="复制">
      
      
// 优化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