→ Smallsh: 大師 08/18 17:49
→ sixB: 好難寫 偷看解答了 08/19 05:50
終於考完試了
題目:
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;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.229.93 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723974506.A.E91.html