更新时间:2022-03-05 03:20:46
描述
设计一个算法,找出只含素因子2,3,5 的第 n 小的数。
符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12...:
我们可以认为 1 也是一个丑数。
在线评测地址:领扣题库官网
样例1
输入:9
输出:10
样例2
输入:1
输出:1
解题思路1:最小堆
算法流程
复杂度分析
代码
import heapq
class Solution:
"""
@param n: An integer
@return: return a integer as description.
"""
def nthUglyNumber(self, n):
heap = []
heapq.heappush(heap, 1)
seen = set()
seen.add(1)
factors = [2, 3, 5]
curr_ugly = 1
for _ in range(n):
# 每次弹出当前最小丑数
curr_ugly = heapq.heappop(heap)
# 生成新的丑数
for f in factors:
new_ugly = curr_ugly * f
if new_ugly not in seen:
seen.add(new_ugly)
heapq.heappush(heap, new_ugly)
return curr_ugly
解题思路2:动态规划
算法流程
重复以下步骤n次,dp[i]表示第i + 1小的丑数:
复杂度分析
代码
import heapq
class Solution:
"""
@param n: An integer
@return: return a integer as description.
"""
def nthUglyNumber(self, n):
dp = [0] * n
dp[0] = 1
l2, l3, l5 = 0, 0, 0
for i in range(1, n):
# 生成第i+1小的丑数
dp[i] = min(2 * dp[l2], 3 * dp[l3], 5 * dp[l5])
if dp[i] == 2 * dp[l2]:
l2 += 1
if dp[i] == 3 * dp[l3]:
l3 += 1
if dp[i] == 5 * dp[l5]:
l5 += 1
return dp[n - 1]
更多题解参考:九章官网solution