作者:whisper
链接:https://www.proprogrammar.com/article/889
声明:请尊重原作者的劳动,如需转载请注明出处
我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1
是丑数。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个数
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论