LeetCode_动态规划_中等_313.超级丑数

1.题目

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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 <= 10⁵
1 <= primes.length <= 100
2 <= primes[i] <= 1000
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都互不相同 ，且按递增顺序排列

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/super-ugly-number

2.思路

本题与LeetCode_动态规划_中等_264.丑数 II这题十分相似，只不过本题的质因数是由题目中的数组 primes 给出。

（1）暴力穷举法
暴力穷举法比较容易想到：
① 如果 n == 1，则直接返回 1，因为 1 通常被视为丑数；
② 否则从正整数 x = 2 开始判断，具体的判断方式可以参考263.丑数这篇文章，如果当前的数是丑数，则 n- -，当 n == 1 时停止判断，此时的 x - 1 就是第 n 个丑数。不过该方法的时间复杂度较高，在 LeetCode 上提交时会出现“超出时间限制”的提示！

（2）最小堆
思路参考本题官方题解。

（3）动态规划
思路参考本题官方题解。

相似题目
LeetCode_因式分解_简单_263.丑数
LeetCode_动态规划_中等_264.丑数 II

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    
    public int nthSuperUglyNumber(int n, int[] primes) {
    
        if (n == 1) {
    
            return 1;
        }
        //从正整数 2 开始判断
        int x = 2;
        int i = 1;
        while (n > 1) {
    
            int tmp = x;
            for (int j = 0; j < primes.length; j++) {
    
                while (tmp % primes[j] == 0) {
    
                    tmp /= primes[j];
                }
            }
            if (tmp == 1) {
    
                n--;
            }
            x++;
        }
        return x - 1;
    }
}

//思路2————最小堆
class Solution {
    
    public int nthSuperUglyNumber(int n, int[] primes) {
    
        if (n == 1) {
    
            return 1;
        }
        Set<Long> hashSet = new HashSet<>();
        // 优先级队列的底层实现原理就是最小堆
        PriorityQueue<Long> heap = new PriorityQueue<>();
        hashSet.add(1L);
        heap.offer(1L);
        int res = 0;
        for (int i = 0; i < n; i++) {
    
            long x = heap.poll();
            res = (int) x;
            for (int prime : primes) {
    
                long nextUgly = x * prime;
                if (hashSet.add(nextUgly)) {
    
                    heap.offer(nextUgly);
                }
            }
        }
        return res;
    }
}

//思路3————动态规划
class Solution {
    
    public int nthSuperUglyNumber(int n, int[] primes) {
    
        // dp[i] 表示第 i 个丑数
        int[] dp = new int[n + 1];
        int m = primes.length;
        int[] pointers = new int[m];
        int[] nums = new int[m];
        // 最小的丑数是 1
        Arrays.fill(nums, 1);
        for (int i = 1; i <= n; i++) {
    
            int minNum = Arrays.stream(nums).min().getAsInt();
            dp[i] = minNum;
            for (int j = 0; j < m; j++) {
    
                if (nums[j] == minNum) {
    
                    pointers[j]++;
                    nums[j] = dp[pointers[j]] * primes[j];
                }
            }
        }
        return dp[n];
    }
}