我们把只包含质因子2、3和5的数称为丑数(Ugly Number)。求按从小到大的顺序的第$n$个丑数。

示例：

输入：n = 10
输出：12
解释：1，2，3，4，5，6，7，8，9，10，12是前10个丑数

说明：

1. 1是丑数
2. n不超过1690

注意：本题与主站264题相同：

class Solution:
	def nthUglyNumber(self, n):

解题思路：

丑数的递推性质：丑数只包含因子2，3，5，因此有”丑数=某较小丑数x某因子“(例如：10 = 5 x 2)

设已知长度为$n$的丑数序列$x_1,x_2,\cdots,x_n$，求第$n+1$个丑数$x_{n+1}$。根据递推性质，丑数$x_{n+1}$只可能是以下三种情况其中之一(索引a,b,c为未知数)：

复杂度分析:

• 时间复杂度$O(N)$：其中$N = n$，动态规划需遍历计算$dp$列表。
• 空间复杂度$O(N)$：长度为$N$的$dp$列表使用$O(N)$的额外空间。

class Solution:
	def nthUglyNumber(self, n):
		dp, a, b, c = [1] * n, 0, 0, 0
		for i in range(1, n):
			n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
			dp[i] = min(n2, n3, n5)
			if dp[i] == n2: a += 1
            if dp[i] == n3: b += 1
            if dp[i] == n5: c += 1
        return dp[-1]