难度 medium
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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是很相似的，可以用同样的方法解决。由于题目给定的质因数不再是2，3，5，而是一个数组，我们也可以用一个数组idx来记录每个质因数的最新idx[i]，idx[i]表示第i个质因数在结果数组dp中的下标，该下标对应的丑数就是第i个质因数为了构建一个新的丑数使用的上一个丑数。当构建出当前丑数的时候，我们利用质因数数组找到构建出当前丑数的上一个丑数的下标，然后更新其下标。其实思路和264. 丑数 II是完全一样的。
代码 t77 s80 java
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int len = primes.length;
int[] dp = new int[n];
dp[0] = 1;
int[] idx = new int[len];
for(int i=1; i<n; i++){
dp[i] = Integer.MAX_VALUE;
for(int j=0; j<len; j++){
// 找到当前最小的丑数
dp[i] = Math.min(dp[i], dp[idx[j]] * primes[j]);
}
for(int j=0; j<len; j++){
// 找到构建出当前丑数的上个丑数的下标，并加一
// 表示那个丑数对应的情况已经涵盖了，需要往后考虑下一个丑数了
if(dp[i]==dp[idx[j]]*primes[j]){
idx[j]++;
}
}
}
return dp[n-1];
}
}
解题思路2：其实这道题目还可以用最小堆的方法解决，堆顶始终是目前构建的所有丑数中的最小值，每次取出当前的最小丑数，并且和质因数数组（也就是初始丑数数组）进行相乘，将得到的新的丑数入堆，直到出堆的丑数个数达到要求。这种方法其实就是无脑暴力方法，只要没达到个数要求，就一直构建丑数，然后利用最小堆的排序功能，每次都取出当前最小丑数，这样相当于就是按顺序排好了所有丑数，直到达到个数要求就返回，多的丑数就不管了。
代码 java t28 s5
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
HashSet<Long> set = new HashSet<>();
PriorityQueue<Long> q = new PriorityQueue<>();
set.add(1L);
q.add(1L);
while(n-->0){
long t = q.poll();
if(n==0) return (int)t;
for(int p : primes){
if(!set.contains(t*p)){
set.add(t*p);
q.add(t*p);
}
}
}
return -1;
}
}
参考资料：
https://www.cnblogs.com/grandyang/p/5144918.html
https://leetcode-cn.com/problems/super-ugly-number/solution/gong-shui-san-xie-yi-ti-shuang-jie-you-x-jyow/