|
刚刚在小红书上研究，怎么做 擂椒茄子松花蛋， 诶，实在是太想吃了。
那么我们就啊开始做每日一题吧，做完就可以睡觉啦！
每日一题： 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开始。
睡觉啦，今天睡觉前一定不玩手机好好睡觉，明天早上吃老干妈炒面～
|