Medium

题目描述

超级丑数是一个正整数，其质因数都在数组 primes 中。

给你一个整数 n 和一个整数数组 primes，请你返回第 n 个超级丑数。

题目数据保证第 n 个超级丑数在 32 位有符号整数范围内。

示例 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 <= 10^5
  • 1 <= primes.length <= 100
  • 2 <= primes[i] <= 1000
  • primes[i] 保证是一个质数
  • primes 中的所有值都 互不相同 ，且按 递增顺序 排列

解题思路

这道题是经典的丑数问题的扩展版本。我们需要生成一个序列，其中每个数都只包含给定质数集合中的因子。

核心思路：动态规划 + 多路归并

  1. 基本思想：每个超级丑数都是由之前的超级丑数乘以某个质数得到的。我们维护一个结果数组，从1开始逐步构建。

  2. 多指针法：为每个质数维护一个指针，指向当前应该与该质数相乘的超级丑数的位置。这样可以确保生成的序列是有序的。

  3. 避免重复：当多个质数产生相同的候选值时，需要同时移动对应的指针，避免重复添加。

  4. 算法步骤：

    • 初始化结果数组，第一个元素为1
    • 为每个质数创建一个指针，初始都指向索引0
    • 每次选择所有候选值中的最小值作为下一个超级丑数
    • 更新所有产生最小值的指针

时间复杂度优化：使用多指针法比暴力枚举或优先队列的方法更高效，时间复杂度为O(n×k)，其中k是质数的个数。

代码实现

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> ugly(n);
        ugly[0] = 1;
        
        vector<int> pointers(primes.size(), 0);
        
        for (int i = 1; i < n; i++) {
            int minVal = INT_MAX;
            for (int j = 0; j < primes.size(); j++) {
                minVal = min(minVal, ugly[pointers[j]] * primes[j]);
            }
            
            ugly[i] = minVal;
            
            for (int j = 0; j < primes.size(); j++) {
                if (ugly[pointers[j]] * primes[j] == minVal) {
                    pointers[j]++;
                }
            }
        }
        
        return ugly[n-1];
    }
};

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        ugly = [1]
        pointers = [0] * len(primes)
        
        for i in range(1, n):
            candidates = [ugly[pointers[j]] * primes[j] for j in range(len(primes))]
            min_val = min(candidates)
            ugly.append(min_val)
            
            for j in range(len(primes)):
                if candidates[j] == min_val:
                    pointers[j] += 1
        
        return ugly[n-1]

public class Solution {
    public int NthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        
        int[] pointers = new int[primes.Length];
        
        for (int i = 1; i < n; i++) {
            int minVal = int.MaxValue;
            for (int j = 0; j < primes.Length; j++) {
                minVal = Math.Min(minVal, ugly[pointers[j]] * primes[j]);
            }
            
            ugly[i] = minVal;
            
            for (int j = 0; j < primes.Length; j++) {
                if (ugly[pointers[j]] * primes[j] == minVal) {
                    pointers[j]++;
                }
            }
        }
        
        return ugly[n-1];
    }
}

/**
 * @param {number} n
 * @param {number[]} primes
 * @return {number}
 */
var nthSuperUglyNumber = function(n, primes) {
    const ugly = [1];
    const indices = new Array(primes.length).fill(0);
    
    for (let i = 1; i < n; i++) {
        const candidates = primes.map((prime, idx) => prime * ugly[indices[idx]]);
        const nextUgly = Math.min(...candidates);
        ugly.push(nextUgly);
        
        for (let j = 0; j < primes.length; j++) {
            if (candidates[j] === nextUgly) {
                indices[j]++;
            }
        }
    }
    
    return ugly[n - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × k)其中 n 是要求的数字位置，k 是质数数组的长度，需要遍历 n-1 次，每次需要检查 k 个候选值
空间复杂度O(n + k)需要存储 n 个超级丑数的数组和 k 个指针数组

相关题目