通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 剑指 Offer 49. 丑数

203人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/889

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。

示例:

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

说明:  

  1. 1 是丑数。
  2. n 不超过1690。

难度:中等;标签:数字;编程语言:C++


其它题解

不会做,数学题很难做,看其它人的题解吧

class Solution {
public:
    // 想法:看的题解,动态规划很强大啊
    int nthUglyNumber(int n) {
        int res[n];
        res[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; i++) {
            // 更新数组
            res[i] = min(res[p2] * 2, min(res[p3] * 3, res[p5] * 5));
            // 移动指针
            if (res[i] >= res[p2] * 2) p2++;
            if (res[i] >= res[p3] * 3) p3++;
            if (res[i] >= res[p5] * 5) p5++;
        }
        return res[n - 1];
    }
};

这里p2, p3, p5是三个位置,最初是开始的位置,不断找最小的数,p2*2, p3*3, p5*5,不断找到最小的,做为下一个数,然后更新p2, p3或者p5(如果不更新到下个位置,px*x=res[i],这样下个数不大于当前的数不行,要下一个最小的数,只要增加一个位置,而且每次加1,一个位置都不会被漏掉,也保证了结果的正确),这样因子为2,3,5的数不断增多,而且是从小到大增加,最后会找到第n个数


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告