力扣（LeetCode） - 313 超级丑数

一、题目

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

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

示例:
输入: 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] 。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-ugly-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、分析

这道题和《剑值offer》上的丑数那道题思路一样。
质数：是指在大于1的自然数中，除了1和它本身以外不再有其他因数
质因数：既是因数又是质数
题目要求出低n个超级丑数，如果从1开始遍历，求每个自然数的所有因数，然后在看其所有质因数是不是在质数列表 primes中，直到找到第n个超级丑数，这样的时间复杂度会非常高。
我们反向思维，从因数出发，只要从质数列表 primes中选取因数，那么乘积自然就是超级丑数。
用质数列表 primes中的数字不断与已经生成的超级丑数进行相乘，得到新的超级丑数。我们需要注意生成丑数的顺序。
用一个数组保存每个 primes中的质因数下一步应该和哪一个超级丑数相乘。

三、代码

    public int nthSuperUglyNumber(int n, int[] primes) {
        if (primes == null || primes.length == 0) {
            return 0;
        }
        int res[] = new int[n]; //保存的超级丑数
        int len = primes.length;
        int next[] = new int[len];  //primes中的每个质因数对应的下一个因数在res中的坐标
        int curSize = 1;
        res[0] = 1;
        while (curSize < n) { //计算n个超级丑数
            int nextNum = Integer.MAX_VALUE;
            for (int i = 0; i < primes.length; i++) { //计算一个超级丑数
                int temp = res[next[i]] * primes[i];
                if (temp < nextNum) {
                    nextNum = temp;
                }
            }
            res[curSize] = nextNum;
            for (int i = 0; i < len; i++) {  //更新因数坐标
                while (res[next[i]] * primes[i] <= res[curSize]) {
                    next[i]++;
                }
            }
            curSize++;
        }
        return res[n - 1];
    }