终于考完试了
题目:
264. Ugly Number II:
ugly number的定义是只由2、3、5三种质因子的数字，给定一个数字n，回传第
n个由小到大的ugly number，例:给定n=6,ugly number由小到大依序为1,2,3,4,5,6
所以回传的数为6
思路:
保持三个固定要被*2, *3, *5的三个min heap，每次比较这三个heap的top乘完对应数后
谁最小，并将最小的乘结果更新为ans，把被乘数从该heap pop出再将anspush进三个
heap，做n次得到的即为解，要注意如果有任两个heap顶部相乘结果相同只能择一使用
后将另一个被乘数pop出来，正解应该是用三个变量对应三种乘数只针对同一个vector
更新
int nthUglyNumber(int n) {
if(n==1){
return 1;
}
priority_queue <int, vector<int>, greater<int>> m2;
priority_queue <int, vector<int>, greater<int>> m3;
priority_queue <int, vector<int>, greater<int>> m5;
m2.push(1);
m3.push(1);
m5.push(1);
int ans=1;
int cnt=1;
int reg=0;
while(cnt!=n){
if(m2.top()*2<m3.top()*3){
ans=m2.top()*2;
reg=2;
}
else if(m2.top()*2>m3.top()*3){
ans=m3.top()*3;
reg=3;
}
else{
ans=m2.top()*2;
reg=2;
m3.pop();
}
if(ans>m5.top()*5){
ans=m5.top()*5;
reg=5;
}
else if(ans==m5.top()*5){
m5.pop();
}
///
cnt++;
if(cnt==n){
return ans;
}
if(reg==2){
m2.pop();
}
else if(reg==3){
m3.pop();
}
else if(reg==5){
m5.pop();
}
m2.push(ans);
m3.push(ans);
m5.push(ans);
}
return ans;
}