# 剑指Offer题解 - Day65
# 剑指 Offer 49. 丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释:1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
1
2
3
2
3
说明:
1是丑数。n不超过1690。
分析：
根据题目描述，所谓丑数，就是质因子只包含2、3、5，需要注意的是，质因子是可以重复的。
从定义我们可以得出以下结论：
- 下一个丑数，只可能是前面某个丑数乘以2，3，5得到，然后求出最小值便是下一个丑数。
- 由于不确定是哪个丑数乘以2，3，5得到下个丑数，因此可以假设：
- 下一个丑数为
n + 1，满足条件n + 1 = Math.min(a * 2, b * 3, c * 5) n + 1是最接近于n的丑数，因此a * 2是首个大于n的丑数；b * 3是首个大于n的丑数；c * 5是首个大于n的丑数。
- 下一个丑数为
本题可以采取动态规划的方式求出最终的丑数。上述的步骤就是动态转移方程。首先来看最终代码：
# 动态规划
/**
* @param {number} n
* @return {number}
*/
var nthUglyNumber = function(n) {
let a = 0;
let b = 0;
let c = 0;
let dp = Array(n);
dp[0] = 1;
for (let i = 1; i < n; i++) {
let n2 = dp[a] * 2;
let n3 = dp[b] * 3;
let n5 = dp[c] * 5;
dp[i] = Math.min(n2, n3, n5);
if(dp[i] === n2) a++;
if(dp[i] === n3) b++;
if(dp[i] === n5) c++;
}
return dp[n - 1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
- 时间复杂度 O(n)。
- 空间复杂度 O(n)。
分析：
初始化三个丑数索引。同时初始化第一个丑数为1。
然后分别计算三个丑数乘以2、3、5的值，并求出最小值。最小的那个数就是当前丑数。然后需要累加求出当前丑数的丑数索引，方便求出下个丑数。动态规划状态转移结束后，返回dp数组的最后一项，便是需要求的丑数。
# 总结
本题考查动态规划。难度系数困难。需要注意的点就是质因子可以重复，以及状态转移的逻辑。
复杂度方面，因为需要遍历来计算dp数组，所以时间复杂度是O(n) ；dp数组占用O(n) 的空间复杂度。