剑指 Offer 49. 丑数 - 力扣（LeetCode）
LeetCode第 264 题：丑数II(C++)_zj-博客
class Solution { public: int nthUglyNumber(int n) { priority_queue<long, vector<long>, greater<long>> q; q.push(1); long val = 0; for(int i = 0; i < n; ++i){ val = q.top(); q.pop(); q.push(val*2); q.push(val*3); q.push(val*5); while(q.top() == val){ q.pop();//去重 } } return val; } };dp:
class Solution { public: int nthUglyNumber(int n) { vector<int> dp(n, 0); dp[0] = 1; int p2 = 0, p3 = p2, p5 = p2; for(int i = 1; i < n; ++i){ dp[i] = min(2*dp[p2], min(3*dp[p3], 5*dp[p5])); if(dp[i] == 2*dp[p2]) ++p2; if(dp[i] == 3*dp[p3]) ++p3; if(dp[i] == 5*dp[p5]) ++p5; } return dp[n-1]; } };