LeetCode刷题实战264：丑数 II
共 2029字，需浏览 5分钟
·
2021-05-15 09:37
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
示例
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1
输出：1
解释：1 通常被视为丑数。
解题
def nthUglyNumber(n):
dp = [0] * n
#第一个丑数为1
dp[0] = 1
#表示下一个丑数是乘以哪个质因子（2，3，5）得到的。
#p2表示乘以2，p3表示乘以3， p5表示乘以5.
p2 = 0
p3 = 0
p5 = 0
#遍历
for i in range(1, n):
dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
#更新对应的指针
if dp[i] == dp[p2] * 2:
p2 += 1
if dp[i] == dp[p3] * 3:
p3 += 1
if dp[i] == dp[p5] * 5:
p5 += 1
print(dp)
return dp[-1]