我们把只包含因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。
class Solution:
def nthUglyNumber(self, n:int)->int:
dp = [1]*n
a, b, c = 0, 0, 0
for i in range(1,n):
n2, n3, n5 = dp[a]*2, dp[b]*3, dp[c]*5
dp[i] = min(n2, n3, n5)
if dp[i] == n2: a += 1
if dp[i] == n3: b += 1
if dp[i] == n5: c += 1
return dp[-1]
时间复杂度 O(N) : 其中 N = n,动态规划需遍历计算 dp列表。
空间复杂度 O(N) : 长度为 N的 dp 列表使用 O(N)的额外空间。