作者：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个数

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