糖逗 发表于 2020-5-18 11:44:02

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;
    }
};

糖逗 发表于 2020-5-18 16:03:19

本帖最后由 糖逗 于 2020-5-18 16:39 编辑

还是建议写成动态规划形式，否则容易超时{:10_284:}

糖逗 发表于 2020-5-18 16:38:49

C++动态规划
class Solution {
public:
    int nthUglyNumber(int n) {
      int temp2 = 0, temp3 = 0, temp5 = 0;
      vector<int> dp(n, 0);
      dp = 1;

      for(int i = 1; i < n; i++){
            int temp =min(dp * 5, min(dp * 2, dp*3));
            if(temp == dp*5)temp5++;
            if(temp == dp*2)temp2++;
            if(temp == dp*3) temp3++;
            dp = temp;
      }
      return dp;
    }
};
页: [1]
查看完整版本: C++刷leetcode（264. 丑数 II）【数据结构】