题目描述
Given an unsorted integer array, find the smallest missing positive integer.
Example1:
Input: [1,2,0] Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
解题思路
- 寻找丢失的正整数
- 我们使用multiset进行初始化，-》 自动有序（如果是自定义类型，需要重载<）
- 从头遍历一个正整数序列（sets最后一个元素即为最大），
- 如果最后元素走到最大的话，我们就可以直接返回下一个元素
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int max = INT_MIN;
multiset<int> sets(nums.begin(), nums.end());
if(sets.size() == 0){
return 1;
}
max = *sets.rbegin(); // 先找到一个最大值
int i = 1;
for(; i <= max; i++){ // 遍历1 - n 这个序列 看是否在这个sets里面
if(sets.count(i) == 0){
return i;
}
}
if(i > max){ // 如果都在，直接返回下一个即可
return i;
}
return 0;
}
};
