題目：
給定一個未排序的整數(shù)數(shù)組铁坎，找出其中沒有出現(xiàn)的最小的正整數(shù)撵幽。
示例 1:
輸入: [1,2,0]
輸出: 3
示例 2:
輸入: [3,4,-1,1]
輸出: 2
示例 3:
輸入: [7,8,9,11,12]
輸出: 1
說明:你的算法的時間復(fù)雜度應(yīng)為O(n)痴荐，并且只能使用常數(shù)級別的空間烘豌。
難度：困難（hard）
題目鏈接：https://leetcode-cn.com/problems/first-missing-positive
思路：
1、由于有時間復(fù)雜度O(n)的要求辙纬，所以只能進行遍歷豁遭，不能進行排序。
2贺拣、首先把數(shù)組中的正數(shù)都拿出來蓖谢，放到字典里，則數(shù)組中沒有出現(xiàn)的最小整數(shù)只可能比數(shù)組中正數(shù)的個數(shù)n小譬涡，所以可以從1到n遍歷一下闪幽，看一下數(shù)字是否在字典里即可知道缺失的最小整數(shù)
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]; // 設(shè)置成長整型避免溢出
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;
}
};