丑数 II（LeetCode）

题目

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

解题

def nthUglyNumber(n: int) -> int:     # 初始化 dp 数组     dp = [0] * n     dp[0] = 1      # 初始化三个指针     p2 = p3 = p5 = 0      for i in range(1, n):         # 计算当前三个候选丑数         next_ugly = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)          # 更新 dp 数组         dp[i] = next_ugly          # 移动指针         if next_ugly == dp[p2] * 2:             p2 += 1         if next_ugly == dp[p3] * 3:             p3 += 1         if next_ugly == dp[p5] * 5:             p5 += 1      return dp[n - 1]   # 测试代码 n = 10 print(f"The {n}th ugly number is: {nthUglyNumber(n)}") 

 The 10th ugly number is: 12