难度: Medium
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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 <= 1051 <= primes.length <= 1002 <= primes[i] <= 1000primes[i] 是一个质数primes 中的所有值都 互不相同 ，且按 递增顺序 排列运行时间: 140 ms
内存: 21.9 MB
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
ans = [1]
ans_idx = [0]
primes_idx = [0 for _ in range(len(primes))]
pq = [(prime, idx) for idx, prime in enumerate(primes)]
heapq.heapify(pq)
for _ in range(n-1):
cur, idx = heapq.heappop(pq)
ans.append(cur)
ans_idx.append(idx)
primes_idx[idx] += 1
while ans_idx[primes_idx[idx]] > idx:
primes_idx[idx] += 1
heapq.heappush(pq, (primes[idx] * ans[primes_idx[idx]], idx))
return ans[-1]
这个题解使用了最小堆来解决超级丑数问题。具体思路如下： 1. 初始化一个结果数组 ans，并将 1 作为第一个超级丑数加入 ans。 2. 使用一个最小堆 pq 存储 (prime, idx) 元组，其中 prime 表示质数，idx 表示该质数在 primes 数组中的下标。最小堆按照 prime 值进行排序。 3. 初始化一个数组 primes_idx，用于记录每个质数在 ans 数组中的下标。 4. 循环 n-1 次，每次从最小堆中取出最小的 (prime, idx) 元组，将 prime 加入 ans 数组。 5. 更新 primes_idx[idx]，找到下一个未被使用的 ans[primes_idx[idx]]，将其与当前质数相乘，得到新的超级丑数，并将其加入最小堆中。 6. 最终返回 ans 数组的最后一个元素，即第 n 个超级丑数。
时间复杂度: O(n * log k)，其中 n 是要求的超级丑数的编号，k 是质数数组的长度。
空间复杂度: O(n + k)，其中 n 是要求的超级丑数的编号，k 是质数数组的长度。
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
ans = [1] # 结果数组，初始化为 [1]
ans_idx = [0] # 记录每个质数在 ans 数组中的下标
primes_idx = [0 for _ in range(len(primes))] # 记录每个质数在 ans 数组中的下标
pq = [(prime, idx) for idx, prime in enumerate(primes)] # 初始化最小堆
heapq.heapify(pq) # 建立最小堆
for _ in range(n-1):
cur, idx = heapq.heappop(pq) # 取出最小的超级丑数及其对应的质数下标
ans.append(cur) # 将当前超级丑数加入结果数组
ans_idx.append(idx) # 记录当前超级丑数对应的质数下标
primes_idx[idx] += 1 # 更新对应质数的下标
while ans_idx[primes_idx[idx]] > idx: # 找到下一个未被使用的 ans[primes_idx[idx]]
primes_idx[idx] += 1
heapq.heappush(pq, (primes[idx] * ans[primes_idx[idx]], idx)) # 将新的超级丑数加入最小堆
return ans[-1] # 返回第 n 个超级丑数
最小堆结构能够有效地从多个质数的乘积结果中持续选出最小的数，保证生成的超级丑数是按顺序排列的。在每次从堆中取出最小元素后，都会生成新的可能的超级丑数并加入堆中，确保下一次仍然可以获取到最小值。使用最小堆可以避免对所有生成的丑数进行排序，从而提高效率。
如果最小堆中存在重复的超级丑数，它可能会稍微影响效率，因为同一个丑数会被多次处理和添加到结果数组中，尽管最终结果数组中不会包含重复的丑数。在实际实现中，可以通过设置或检查条件来避免将重复的丑数加入到最小堆中，从而优化算法的效率。
这一步骤的目的是为了确保每个质数都能乘以所有可能的先前生成的超级丑数，从而生成所有可能的新超级丑数。通过更新`primes_idx[idx]`，我们确保每个质数都与它之前的所有超级丑数相乘，这样可以保持超级丑数数组的完整性和正确性。
对应元素是通过质数的索引`idx`在`primes_idx`数组中的值来确定的。每次从堆中取出一个元素时，都会使用对应质数与ans数组中`primes_idx[idx]`位置的元素相乘，生成新的超级丑数。这确保了每个质数都依次与所有生成的超级丑数相乘，从而按正确的顺序生成每一个新的超级丑数。