leetcode--41--缺失的第一个正数

题目：
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3
示例 2:

输入: [3,4,-1,1]
输出: 2
示例 3:

输入: [7,8,9,11,12]
输出: 1

说明:你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
难度：困难（hard）
题目链接：https://leetcode-cn.com/problems/first-missing-positive

思路：
1、由于有时间复杂度O(n)的要求，所以只能进行遍历，不能进行排序。
2、首先把数组中的正数都拿出来，放到字典里，则数组中没有出现的最小整数只可能比数组中正数的个数n小，所以可以从1到n遍历一下，看一下数字是否在字典里即可知道缺失的最小整数

Python代码：

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 1

        nums_pos = {}
        max_num = nums[0]
        for num in nums:
            if num<0:
                continue
            nums_pos[num] = 0
            max_num = max(max_num, num)

        if max_num<=0:
            return 1

        ret = max_num+1
        for item in range(1, len(nums_pos)+1):
            if item not in nums_pos:
                ret = item
                break
    
        return ret

C++代码：

using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if (nums.empty()){
            return {1};
        }
        map<int,int> dt;
        long long int max_num = nums[0];    // 设置成长整型避免溢出

        for(long long int item : nums){
            if (item<0){
                continue;
            }
            dt[item] = 0;
            max_num = std::max(max_num, item);
        }

        if (max_num<=0){
            return {1};
        }
        long long int ret = (long long int)(max_num+1);    
        for(int j=1; j<=dt.size(); j++){
            if (dt.find(j)==dt.end()){
                ret = j;
                break;
            }
        }
        return ret;
    }
};