【python】Leetcode每日一题-丑数2

【python】Leetcode每日一题-丑数2

【题目描述】

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

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

示例1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。


示例2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。


提示：

1 <= n <= 1690


【分析】

• dp

  思路就是开一个数组，若x为丑数，则2x、3x、5x均为丑数，现将2x、3x、5x称为x的直接生成丑数。现使用三个指针（point2、point3、point5）分别指向数组中丑数，若2x已经加入到数组中，则称x的point2已使用，则point2指针后移，现只需维护这三个指针，则可以保证2x、3x、5x一定不在数组中，每次取其中最小值，则可以保证数组单调递增。

• 代码

class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1
p2 = p3 = p5 = 1 for i in range(2, n + 1):
num2, num3, num5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
dp[i] = min(num2, num3, num5)
if dp[i] == num2:
p2 += 1
if dp[i] == num3:
p3 += 1
if dp[i] == num5:
p5 += 1
return dp[n]


• 小顶堆（优先队列）

  即使用小顶堆作为存储丑数的容器，每次取丑数并增加3个生成丑数时维护更新小顶堆即可，相当于暴力解法中sort改为更方便快捷的小顶堆更新。

  class Solution:
def nthUglyNumber(self, n: int) -> int:
factors = [2, 3, 5]
seen = {1}
heap = [1] for i in range(n - 1):
curr = heapq.heappop(heap)
for factor in factors:
if (nxt := curr * factor) not in seen:
seen.add(nxt)
heapq.heappush(heap, nxt) return heapq.heappop(heap)