丑数

该题解采用了动态规划的方法来解决丑数问题。首先创建一个长度为 n 的数组 dp，其中 dp[i] 存储第 i+1 个丑数。初始化 dp[0] 为 1，因为 1 是第一个丑数。接着使用三个指针 a、b、c 分别指向数组中某个确定的位置，这些位置对应的元素乘以 2、3、5 后可以生成新的丑数。每次循环计算出三个可能的丑数 n2, n3, n5（分别为 dp[a]*2, dp[b]*3, dp[c]*5），取这三个数中最小的一个作为新的丑数添加到 dp 数组中。然后根据所选的丑数来更新对应的指针（如果新丑数等于 n2，则移动 a 指针；如果等于 n3，则移动 b 指针；如果等于 n5，则移动 c 指针）。这样可以保证数组 dp 按从小到大的顺序存储每一个丑数，直到填满。最后 dp[n-1] 就是第 n 个丑数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [1] * n  # 初始化dp数组，dp[i]表示第i+1个丑数
        a, b, c = 0, 0, 0  # 初始化三个指针，分别对应质因数2，3，5
        for i in range(1, n):
            n2, n3, n5 = 2*dp[a], 3*dp[b], 5*dp[c]  # 分别计算三个新的可能的丑数
            dp[i] = min(n2, n3, n5)  # 选择最小的一个作为新的丑数
            if dp[i] == n2:
                a += 1  # 如果选中的是2*dp[a]，则将指针a向前移动
            if dp[i] == n3:
                b += 1  # 如果选中的是3*dp[b]，则将指针b向前移动
            if dp[i] == n5:
                c += 1  # 如果选中的是5*dp[c]，则将指针c向前移动
        return dp[-1]  # 返回第n个丑数

if __name__ == '__main__':
    s = Solution()
    s.nthUglyNumber(10)  # 测试函数