题目
给定一个数组, 查找数组中丢失的最小正整数.
要求时间复杂度O(n), 空间复杂度为常数.
Input: [1,2,0]
Output: 3
Input: [3,4,-1,1]
Output: 2
Input: [1,1,2]
Output: 3
解析
首先可能想到DP, 但是DP不可能满足时间复杂度.
然后想到使用set或者stack方法, 好像也不行.
最后通过map, 可以很简单的解决这个问题.
思路
采用map记录给定的数, 然后循环0到n, 如果map没有该数即为结果.
int firstMissingPositive(vector<int>& nums) {
map<int, bool> dic;
for(int i = 0; i < nums.size(); i++) {
int a = nums[i];
if (a <= 0) continue;
dic[a] = true;
}
int res = 0;
while (dic[++res]) {}
return res;
}
总结
总体来说, 这个题目很简单, 但是居然是一道hard
的题.
主要还是熟练掌握各种数据结构的使用场景.
网友评论