313. 超级丑数

Difficulty
Medium
Tags
多路归并
URL
https://leetcode-cn.com/problems/super-ugly-number/
Star
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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 中的所有值都 互不相同 ，且按 递增顺序 排列

法 1 多路归并

思路
参考
🥍
264. 丑数 II ，本题是质数不只有三个了，所以需要专门用一个数字维护。
时间复杂度 O(nm)
题解
class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        idx = [0]  * len(primes)
        res = [0] * n
        res[0] = 1
        
        for i in range(1, n):
            # 计算 候选数字, 并且计算出是哪个的贡献
            min_val, min_idx = float("inf"), []
            for j in range(len(primes)):
                temp = res[idx[j]] * primes[j]
                
                if temp < min_val:
                    min_val = temp
                    min_idx = []
                    min_idx.append(j)
                elif temp == min_val:
                    min_idx.append(j)
            
            # 对选中的下标 加 1
            for k in min_idx:
                idx[k] += 1
						# 得到当前的结果
            res[i] = min_val
        
        return res[n-1]

法 2 优先队列

思路
类似
🥍
264. 丑数 II ，使用优先队列，弹出 n 个丑数，第 n 个丑数就是答案。会超时！！
题解
import heapq
class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        h = []
        visited = set()
        heapq.heappush(h, 1)
        while True:
            x = heapq.heappop(h)
            n -= 1
            if n == 0:
                return x

            for p in primes:
                t = p * x
                if t not in visited:
                    visited.add(t)
                    heapq.heappush(h, t)