给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
[1,2,0]
3
[3,4,-1,1]
2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为 \(\mathcal{O}(n)\),并且只能使用常数级别的空间。
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
int max = 0;
for (int i = 0; i < n; i++)
if (nums[i] > max) max = nums[i];
bool flags[max+2] = {false};
for (int i = 0; i < n; i++) {
int num = nums[i];
if(num > 0) flags[num] = true;
}
if (n > 0) {
for (int i = 1; i <= max+1; i++)
if (!flags[i]) return i;
} else
return 1;
}
原文:https://www.cnblogs.com/4thirteen2one/p/9823688.html