313. Super Ugly Number

题目描述和难度

  • 题目描述：

编写一段程序来查找第 n 个超级丑数。

超级丑数是指其所有质因数都在长度为 k 的质数列表 primes 中的正整数。

示例:

输入: n = 12, primes = [2,7,13,19]
输出: 32 
解释: [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]，是给定长度为 4 的 质数列表 primes = [2,7,13,19]的前 12 个超级丑数。

说明:

  • 1 是任何给定 primes 的超级丑数。
  •  给定 primes 中的数字以升序排列。
  • 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
  • 第 n 个超级丑数确保在 32 位有符整数的范围内。

思路分析

求解关键：

参考解答

参考解答1

public class Solution {

    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] dp = new int[n];
        int plen = primes.length;
        if (n <= 0 || plen == 0) {
            return 0;
        }
        int[] indexes = new int[primes.length];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < plen; j++) {
                dp[i] = Integer.min(dp[i], dp[indexes[j]] * primes[j]);
            }
            for (int j = 0; j < plen; j++) {
                if (dp[i] == dp[indexes[j]] * primes[j]) {
                    indexes[j]++;
                }
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        int n = 12;
        int[] nums = {2, 7, 13, 19};
        Solution solution = new Solution();
        int nthSuperUglyNumber = solution.nthSuperUglyNumber(n, nums);
        System.out.println(nthSuperUglyNumber);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0313-super-ugly-number ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。