LeetCode 41. First Missing Positive

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 41. First Missing Positive 原题链接困难

作者：

extrovert , 2018-04-03 23:30:07 , 所有人可见 , 阅读 3870

43

15

题目描述

给定一个无序的整数序列，找到第一个缺失的正整数。
要求时间复杂度为 $O(n)$ ，使用常数空间。

样例

输入[1,2,0]，返回3
输入[3,4,-1,1]，返回2

算法

(桶排序) $O(n)$ Time, $O(1)$ Space

不用额外空间的桶排序：保证1出现在nums[0]的位置上，2出现在nums[1]的位置上，…，n出现在nums[n-1]的位置上，其他的数字不管。例如[3,4,-1,1]将被排序为[1,-1,3,4]
遍历nums，找到第一个不在应在位置上的1到n的数。例如，排序后的[1,-1,3,4]中第一个 nums[i] != i + 1 的是数字2（注意此时i=1）。

时间复杂度分析：代码中第二层while循环，每循环一次，会将一个数放在正确的位置上，所以总共最多执行 $n$ 次，所以总时间复杂度 $O(n)$ 。

C++

class Solution{
public:
    int firstMissingPositive(vector<int>& nums) 
    {
        int n = nums.size();

        for(int i = 0; i < n; ++ i)
            while(nums[i] > 0 && nums[i] <= n
                    && nums[nums[i] - 1] != nums[i])
                swap(nums[i], nums[nums[i] - 1]);

        for(int i = 0; i < n; ++ i)
            if(nums[i] != i + 1)
                return i + 1;

        return n + 1;
    }
};

8 评论

ninglei 2021-08-22 08:11

“代码中第二层while循环，每循环一次，会将一个数放在正确的位置上”
这句话点破重点。

JIeJaitt 2022-03-15 12:24

这个排序写的比y总写的好一点

traveleryyk 2020-07-03 18:42

好厉害qaq

Stella-W 2020-03-08 18:09

while可以替换成if么

我要番茄锅 2020-06-23 08:38

不可以，因为交换后，当前位置出现的新数也需要同样的判断

sysml 2019-06-10 21:18

    int firstMissingPositive(vector<int>& nums) {
        if(nums.size()==0) return 1;
        int n=nums.size();
        for(auto &c:nums){
             if(c<=0 || c>n){ 
                c=0;
                continue;
            }
        }
        for(auto &c:nums){
            if(c==0 || abs(c)>n) continue;  
            auto pos=(labs(c)-1);
            if(nums[pos]==0) nums[pos]=-(n+2); 
            else nums[pos]=-abs(nums[pos]);
        }
        for(int i=0;i<nums.size();i++){
            if(nums[i]>=0) return i+1;
        }
        return n+1; 
    }