刚刚在小红书上研究,怎么做 擂椒茄子松花蛋, 诶,实在是太想吃了。 那么我们就啊开始做每日一题吧,做完就可以睡觉啦!
每日一题: 313.超级丑数
题目描述:
https://leetcode-cn.com/problems/super-ugly-number 超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ,返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
示例 1:
输入:n = 12, primes = [2,7,13,19]
输出:32
解释:给定长度为 4 的质数数组 primes = [2,7,13,19],前 12 个超级丑数序列为:[1,2,4,7,8,13,14,16,19,26,28,32] 。
示例 2:
输入:n = 1, primes = [2,3,5]
输出:1
解释:1 不含质因数,因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
提示:
1 <= n <= 106 1 <= primes.length <= 100 2 <= primes[i] <= 1000 题目数据 保证 primes[i] 是一个质数 primes 中的所有值都 互不相同 ,且按 递增顺序 排列
思路
用时: 11:25 - 思路: 感觉是一个二维动态规划的题目。 以第一个例子为例: 第一个丑数肯定是1 ,可以直接return 然后就是对丑数进行排序,然后就是一个循环 比如 [3,13] ? [3,9,13] 所以: [1,13,133,113] [39,313] [99,913] [13*13] –> 感觉啊,还是一筹莫展 [2,3,5,7]
看n的范围,我就知道我没戏了,看答案吧 然后发现我的思路是对的,就是太菜了不会实现呢
官方题解: 最小堆
要得到从小到大的第n个超级丑数,可以使用最小堆实现。 初始时,堆为空。将最小的超级丑数1加入堆。 每次取出堆顶元素x,x是堆中最小的超级丑数, 对于数组primes的任意质数p,px也是超级丑数,所以将primes的每个质数与x的乘积分别入堆。 上述做法会导致堆中出现重复元素,为了避免,可以用哈希集合去重,避免相同元素多次入堆。
在排除重复元素的情况下,第n次从最小堆中取出的元素是第n个超级丑数。
疑问: 其实我不太明白,我怎么知道堆中的元素够了呢?-- 所以生成nm个
from collections import heapq
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
seen = {1}
heap = [1]
for i in range(n):
ugly = heapq.heappop(heap)
for prime in primes:
nxt = prime * ugly
if nxt not in seen:
seen.add(nxt)
heapq.heappush(heap,nxt)
return ugly
时间复杂度:O(nmlognm),其中n为待求的超级丑数的编号,m是primes数组的长度,要得到第n个超级丑数,需要进行n次循环,每次循环要从最小堆中取出一个元素,以及最小堆中加入最多m个元素,因此每次循环的时间复杂度: O(lognm + mlognm) = O(mlognm),所以总的时间复杂度为:O(nmlognm)。 空间复杂度: O(mn),其中n为待求的超级丑数的编号,m是primes数组的长度.空间复杂度取决于最小堆和哈希集合的大小,最小堆和哈希集合的大小都不会超过nm。
官方题解:动态规划
方法一使用最小堆,会预先存储比较多的超级丑数,空间复杂度比较高,维护最小堆的过程也导致时间复杂度比较高,所以使用动态规划进行优化。
定义数组dp,其中dp[i]是第i个超级丑数,第n个超级丑数为dp[n]
最小的超级丑数是1,dp[1] =1
如何得到其余的超级丑数呢?创建和数组primes登场的数组 pointers,表示下一个超级丑数是当前指针指向的超级丑数乘以对应的质因数。初始时,数组 pointers的元素都是1.
当
2
≤
i
≤
2 \leq i \leq
2≤i≤ 时,令
d
p
[
i
]
=
m
i
n
0
≤
j
<
m
d
p
[
p
o
i
n
t
e
r
[
j
]
]
x
p
r
i
m
e
s
[
j
]
dp[i] = min_{0 \leq j < m}{dp[pointer[j]] x primes[j]}
dp[i]=min0≤j<m?dp[pointer[j]]xprimes[j], 然后比较dp[i] 和 dp[pointer[j] x primes[j] 是否相等,相等 pointer[j] +1 。
时间复杂度:O(mn),其中n为待求的超级丑数的编号,m是primes数组的长度,需要计算数组dp个元素,每个元素的计算时间需要O(m) 空间复杂度:O(m+n),其中n为待求的超级丑数的编号,m是primes数组的长度,需要创建数组dp,和数组pointers,空间为O(n)和O(m)。
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
if n == 1:
return 1
dp = [0 for i in range(n+1)]
dp[1] = 1
pointers = [1 for prime in primes]
m = len(primes)
for i in range(2,n+1):
new_num = min(p1*dp[p2] for p1,p2 in zip(primes,pointers))
for j in range(m):
if primes[j] * dp[pointers[j]] == new_num:
pointers[j] += 1
dp[i] = new_num
return int(dp[-1])
– 注意index从1开始。
睡觉啦,今天睡觉前一定不玩手机好好睡觉,明天早上吃老干妈炒面~
|