剑指offer面试题49. 丑数

题目描述

我们把只包含因子 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)的额外空间。