题目：剑指 Offer 49. 丑数 - 力扣（Leetcode）
题目的接口：
class Solution { public: int nthUglyNumber(int n) { } };
解题思路：
丑数这道题用到一点动态规划的思想，
具体思路如下：
根据题意：
如果说第一个丑数是一，包含质因子 2、3 和 5 的数称作丑数，
那么我们发现，之后的丑数：
1, 2, 3, 4, 5, 6, 8, 9, 10, 12
是前 10 个丑数。
都是前面的丑数乘2、乘3或者乘5 得来的，
那我们的思路就能变成：
从第一个数1开始，让他乘2、乘3、乘5，
第二个数也这样操作，
然后取他们的最小值作为下一个丑数，
以此类推，
三个指针，分别用来乘2、乘3、乘5，
取得最小值的那个指针指向下一个数，
如果出现两个数相等的情况，
例：
2 * 5 == 5 * 2
那就两个指针都指向下一个数，
防止重复，
最后返回第n个丑数即可。
例：
根据规则：从第一个数1开始，让他乘2、乘3、乘5
一乘二，指针往后走一个：
一乘三，指针往后走一个：
这个时候，二乘二比一乘五更小，
所以这里走的是二乘二：
然后是一乘五：
以此类推，就能计算出之后的丑数了。
下面是代码：
代码：
class Solution { public: int nthUglyNumber(int n) { //创建n + 1大小的数组 vector dp(n + 1); //初始化三指针 int a = 0, b = 0, c = 0; //数组从1开始 dp[0] = 1; //循环 for(int i = 1; i < n; i++) { //让三指针*2 *3 *5 并选出最小值，就是下一个丑数 int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5; //取最小值 dp[i] = min(min(n2, n3), n5); //如果该下标对应的数是下一个丑数，就让指针指向下一个 //如果有两个数结果相同，就让那两个指针都指向下一个 //防止重复 if(n2 == dp[i]) { a++; } if(n3 == dp[i]) { b++; } if(n5 == dp[i]) { c++; } } //最后返回第n个丑数 return dp[n - 1]; } };
过啦！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
