C++刷leetcode（264. 丑数 II）【数据结构】

糖逗

题目描述：

1. 编写一个程序，找出第 n 个丑数。
   
2. 
   
3. 丑数就是质因数只包含 2, 3, 5 的正整数。
   
4. 
   
5. 示例:
   
6. 
   
7. 输入: n = 10
   
8. 输出: 12
   
9. 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
   
10. 说明:  
    
11. 
    
12. 1 是丑数。
    
13. n 不超过1690。
    
14. 
    
15. 来源：力扣（LeetCode）
    
16. 链接：https://leetcode-cn.com/problems/ugly-number-ii
    
17. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int nthUglyNumber(int n) {
   
4.         priority_queue <double,vector<double>,greater<double> > q;
   
5.         double res = 1;
   
6.         for (int i = 1;i < n; i++){//注意i是从1开始
   
7.             q.push(res * 2);
   
8.             q.push(res * 3);
   
9.             q.push(res * 5);
   
10.             res = q.top();
    
11.             q.pop();
    
12.             while (!q.empty() && res == q.top()){//去重
    
13.                 q.pop();
    
14.             }  
    
15.         }
    
16.         return res;
    
17.     }
    
18. };

复制代码

糖逗

还是建议写成动态规划形式，否则容易超时

糖逗

C++动态规划

1. class Solution {
   
2. public:
   
3.     int nthUglyNumber(int n) {
   
4.         int temp2 = 0, temp3 = 0, temp5 = 0;
   
5.         vector<int> dp(n, 0);
   
6.         dp[0] = 1;
   
7. 
   
8.         for(int i = 1; i < n; i++){
   
9.             int temp =min(dp[temp5] * 5, min(dp[temp2] * 2, dp[temp3]*3));
   
10.             if(temp == dp[temp5]*5)temp5++;
    
11.             if(temp == dp[temp2]*2)temp2++;
    
12.             if(temp == dp[temp3]*3) temp3++;
    
13.             dp[i] = temp;
    
14.         }
    
15.         return dp[n-1];
    
16.     }
    
17. };

复制代码