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

糖逗

题目描述：

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:  

1 是丑数。
n 不超过1690。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue <double,vector<double>,greater<double> > q;
        double res = 1;
        for (int i = 1;i < n; i++){//注意i是从1开始
            q.push(res * 2);
            q.push(res * 3);
            q.push(res * 5);
            res = q.top();
            q.pop();
            while (!q.empty() && res == q.top()){//去重
                q.pop();
            }  
        }
        return res;
    }
};

糖逗

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

糖逗

C++动态规划

class Solution {
public:
    int nthUglyNumber(int n) {
        int temp2 = 0, temp3 = 0, temp5 = 0;
        vector<int> dp(n, 0);
        dp[0] = 1;

        for(int i = 1; i < n; i++){
            int temp =min(dp[temp5] * 5, min(dp[temp2] * 2, dp[temp3]*3));
            if(temp == dp[temp5]*5)temp5++;
            if(temp == dp[temp2]*2)temp2++;
            if(temp == dp[temp3]*3) temp3++;
            dp[i] = temp;
        } 
        return dp[n-1];
    }
};