题目描述
给你一个整数 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
解题思路
- 动态规划数组：dp 数组用于存储从第 1 个到第 n 个丑数。dp[0] 初始化为 1，因为第一个丑数定义为 1。
- 三个指针：p2、p3、p5 分别表示下一个丑数是当前指向的丑数乘以 2、3 或 5。开始时，这三个指针都指向第一个丑数。
- 生成新的丑数：在每一步中，计算 dp[p2] * 2、dp[p3] * 3 和 dp[p5] * 5，并取这三个值中的最小值作为新的丑数。这保证了丑数序列的有序性。
- 更新指针：如果当前丑数是由某个指针生成的（即等于该指针对应的乘积），则将该指针后移一位。这样做是为了确保每个指针都能继续参与生成更大的丑数。
- 结果：循环结束后，dp[n-1] 存储的是第 n 个丑数。
代码实现
class Solution:def nthUglyNumber(self, n: int) -> int:dp = [0] * n # 初始化DP数组，用于存储丑数dp[0] = 1 # 第一个丑数是1# 初始化三个指针，分别对应乘以2、3和5的情况p2, p3, p5 = 0, 0, 0for i in range(1, n):# 选出当前可以生成的最小丑数dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)# 更新指针，如果当前丑数由某个指针生成，则该指针后移if dp[i] == dp[p2] * 2: p2 += 1if dp[i] == dp[p3] * 3: p3 += 1if dp[i] == dp[p5] * 5: p5 += 1return dp[n-1] # 返回第n个丑数
