纸老虎一个
这题的数据范围表明这题应该用 $O(nlogn)$ 的算法来做
所以 O(n) 的都不是正解
扯淡部分结束
我们从数据结构角度来看:
需要满足:
1. 加入一个数
2. 判断这个数是否出现
在此情况下,平衡树 $set$ 可以完美地满足要求
所以做起来就很简单了~
class Solution {
public:
int findMissMin(vector<int>& nums) {
set<int> s ;
for(auto i:nums) s.insert(i) ;
for(int i=1;;i++)
if(s.find(i)==s.end()) return i ;
return -1 ;
}
};
优化:
1. 过滤小于0的数(求的是正整数)
2. 如果存在大于数组长度的数直接排除
为什么?因为如果有一个数大于数组长度,那么答案小于等于数组长度,大于数组长度的数不用考虑
进一步解释,设数组长度为n,那么为了使得答案大于n,答案的前面需要至少有n个数,数值必须是1到n各一个,而因为有一个数已经大于n了,所以说答案小于等于n
让我们再次审视这个问题:
需要满足:
1. 加入一个数
2. 判断这个数是否出现
其实有一种被忽略的答案:用数组存每个数是否出现的信息
可惜我们以为这是会爆空间的,于是放弃了这种想法
回过头来看,既然排除了所有大于数组长度的数,那么这种看似被 $-10^9 \le a_{i} \le 10^9$ 这一栏数据屏蔽掉的方法其实是可行的???
这就是为什么我说这是“纸老虎”
这题的数据范围表明这题应该用 $O(nlogn)$ 的算法来做
所以 O(n) 的都不是正解
看来我错了
最终成品奉上~
class Solution {
public:
int findMissMin(vector<int>& nums) {
bool *st=new bool[nums.size()+10] ;
for(auto i:nums) if(i>0&&i<=nums.size()) st[i]=true ;
for(int i=1;;i++)
if(!st[i]) return i ;
return -1 ;
}
};
记得点赞~ 这是我最大的动力~