题目描述（中等）
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1
输出：1
解释：1 通常被视为丑数。
提示：
1 <= n <= 1690
前情提要——丑数1
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
代码（判断丑数）
class Solution {
public:
bool isUgly(int n) {
if(n < 1) return false;
if(n == 1) return true;
if(n%2 == 0) return isUgly(n/2);
if(n%3 == 0) return isUgly(n/3);
if(n%5 == 0) return isUgly(n/5);
return false;
}
};
思路
暴力计算判断每个数，这样肯定超时，所以就需要其他思想和动态规划了
丑数可以理解为2，3，5的合数，以及前面那几个边界点
简单写一下前几个就是 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 …
素数筛的思想是：筛去不是素数的正整数（也就是合数）,剩下的就是素数
这里反向利用一下，把合数记下来就是答案了，而且只需要2 3 5的合数
需要的素数合集为{2,3,5},每次分别乘合集中的元素
1 打头，1 乘 2 1 乘 3 1 乘 5，现在是 {1,2,3,5}
轮到 2，2 乘 2 2 乘 3 2 乘 5，现在是 {1,2,3,4,5,6,10}
然后问题就是大小比较了,每次存最小的进去，这里就需要动态规划了
设 3 个指针 a2,a3,a5
代表的是第几个数的2倍、3 倍、5 倍
动态方程 dp[i]=min(dp[p_2]*2,dp[p_3]*3,dp[p_5]*5)
代码
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> ugly(n,1);
int a2=0,a3=0,a5=0;
for(int i = 1; i < n ; i++) {
ugly[i] = min(2*ugly[a2],min(3*ugly[a3],5*ugly[a5]));
if(ugly[i] == 2*ugly[a2]) a2++;
if(ugly[i] == 3*ugly[a3]) a3++;
if(ugly[i] == 5*ugly[a5]) a5++;
}
return ugly[n-1];
}
};
结果
