leetcode_first_missing_positive

发表于

难度：Hard
Hard又如何？只要不是动态规划。。

题目要求：
O(n)时间，可以用常量空间。
解题思路：
先找出最大值max，然后申请大小max+1的hash数组，将原始数组映射过来。遍历一遍hash数组，第一个没有映射过来的就是解。
为什么要申请max+1的大小，因为[1,2,3,4]这种情况，第一个需要补的正数是5，所以需要多一位来检查。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int max = INT_MIN;
        for(auto it = nums.begin();it != nums.end(); it++)
        {
            if(*it>max && *it > 0)
                max = *it;
        }
        if(max < 1)
            return 1;
        int min = 1;
        vector<int> match_nums(max-min+2);
        for(auto it = nums.begin();it != nums.end(); it++)
        {
            if(*it > 0)
                match_nums[*it-min] = 1;
        }
        int ret = 1;
        for(auto match_nums_it = match_nums.begin(); match_nums_it != match_nums.end(); match_nums_it++)
        {
            if(*match_nums_it == 0)
            {
                ret =  match_nums_it - match_nums.begin() + min;
                break;
            }
        }
        return ret;
    }
};

运行结果：3ms，超过21.74%