剑指 Offer 49. 丑数
264. 丑数 II
一个题
维护一个小根堆
class Solution {
public:
int nthUglyNumber(int n) {
// 小根堆
priority_queue<long long,vector<long long>,greater<long long> >q;
set<long long> S;
vector<int>factor={2,3,5};
q.push(1),S.insert(1);
long long res=0;
while(n--){
res=q.top();
q.pop();
if(n==0)return res;
for(auto i:factor){
long long tmp=(long long)res*i;
if(S.find(tmp)==S.end()){
q.push(tmp);
S.insert(tmp);
}
}
}
return res;
}
};
