难度：中等

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

示例：

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

解题思路：
来自LeetCode大佬：https://leetcode-cn.com/problems/chou-shu-lcof/solution/chou-shu-ii-qing-xi-de-tui-dao-si-lu-by-mrsate/

python代码：

# 动态规划
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        l1, l2, l3 = 0, 0, 0
        dp = [1] * n
        for i in range(1, n):
            dp[i] = min(dp[l1] * 2, dp[l2] * 3, dp[l3] * 5)
            if dp[i] == dp[l1] * 2: l1 += 1
            if dp[i] == dp[l2] * 3: l2 += 1
            if dp[i] == dp[l3] * 5: l3 += 1
        return dp[-1]

复杂度分析：

• 时间复杂度 O ( N ) O(N) O(N)： N N N是需要遍历数目 n n n；
• 空间复杂度 O ( N ) O(N) O(N)：定义了存储丑数的数组 d p dp dp。