Leetcode 41 First Missing Positive 正解不是盛传的桶排序

Given an unsorted integer array, find the first missing positive integer.

For example,

Given [1,2,0] return 3,

and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

找出第一个缺失的正数。

一开始想用等差数列求和减去实际和的方法，后来发现测试数据中有重复的元素，

于是现学现用想到了复杂度常数级别的unordered_map.

https://cloud.tencent.com/developer/article/1019300

后来发现几乎所有人都用的桶排序，然而我的方法还是比他们快！97.88%哦

代码语言：javascript复制

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) 
    {
        unordered_map<int,int> mp;
        for(int i=0;i<nums.size();i  )
        {
            if(nums[i]>0)
                mp[nums[i]]=1;
        }
        int result=1;
        for(int i=1;i<=nums.size() 1;i  )
        {
            if(!mp[i])
            {
                result=i;
                break;
            }
        }
        return result;
    }
};

algorithm integer map return time

0 人点赞