题目描述
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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^6 1 <= primes.length <= 100 2 <= primes[i] <= 1000 题目数据 保证 primes[i] 是一个质数 primes 中的所有值都 互不相同 ，且按 递增顺序 排列
链接：https://leetcode-cn.com/problems/super-ugly-number
方法一、小顶堆
我们可以把所有可能的元素都存储到小顶堆中，这样我们从小顶堆弹出的第N个元素，就是我们要的结果。
那么，这些可能的元素从哪来呢？
首先，第一个元素肯定是1。
然后，拿到这个1与primes数组中每个元素相乘得到一批可能的元素，让他们入堆。
接着，从堆中弹出一个最小的元素，这个元素再与primes数组中每个元素相乘得到一批可能的元素，让他们入堆。
重复执行上面的逻辑，直到弹出第n个元素即可。
代码如下，由于n的范围是小于10^6，所以有可能溢出，这里使用long类型解决：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
if (n == 1) {
return 1;
}
// 小顶堆，初始值1入堆
// 用long类型防溢出
PriorityQueue<Long> heap = new PriorityQueue<>();
heap.offer(1L);
// 用于去重
long last = -1;
for (int i = 0; i < n; i++) {
long curr = heap.poll();
// 用于去重
while (curr == last) {
curr = heap.poll();
}
// 返回结果
if (i == n - 1) {
return (int) curr;
}
// 每次拿最小的值与数组primes中的每个元素相乘再入堆
for (int j = 0; j < primes.length; j++) {
heap.offer(curr * primes[j]);
}
// 记录上一次的值
last = curr;
}
return 0;
}
}
时间复杂度： O(n*m*log(n*m))
，需要遍历n次，每次向小顶堆中插入m个元素，每个元素插入需要log(nm)的时间复杂度，如果n特别大，这个小顶堆最后会变得非常大。空间复杂度： O(n*m)
，小顶堆中元素趋于n*m`个。
运行结果：
方法二、动态规划
通过观察可以看到，后面的丑数都是通过前面的丑数乘以一个倍数得来的，这个倍数一开始是1，然后是丑数的第一个数，然后是丑数的第二个数，依次进行。
我们以primes = [2,7,13,19]
为例，以ans[]
表示结果：
第一个丑数恒定为1，结果 ans=[1]第二个丑数为 ans[0] * [2,7,13,19]
中的最小数，也就是2，结果ans=[1,2]第三个丑数为 ans[1] * [2] || ans[0] * [7,13,19]
中的最小数，也就是4，结果ans=[1,2,4]第四个丑数为 ans[2] * [2] || ans[0] * [7,13,19]
中的最小数，也就是7，结果ans=[1,2,4,7]第五个丑数为 ans[2] * [2] || ans[1] * [7] || ans[0] * [13,19]
，也就是8，结果ans=[1,2,4,7,8]第六个丑数为 ans[3] * [2] || ans[1] * [7] || ans[0] * [13,19]
，也就是13，结果ans=[1,2,4,7,8,13]
依次类推，可以看到，一个数一旦被乘了以后，下一次乘以它的数就是当前乘以它的那个丑数的下一个丑数，比如2的倍数的丑数依次为：2，4，8，14，16，26，所以，我们可以使用一个数组pointer管理每个丑数已经被乘过几次了，而这个几次正好对应到ans
结果数组中的下标。
我们将这个ans数组换成dp数组，并且下标从1开始，就是动态规划了：
状态定义： dp[i]表示第i个丑数，i从1开始，dp[1]=1状态转移： dp[i] = min(dp[pointer[i]] * primes[i])，pointer[i]表示被乘过几次了，以pointer[i]作为dp的下标正好表示这一次轮到第几个丑数来与primes[i]相乘了
代码如下，注意去重：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
if (n == 1) {
return 1;
}
int m = primes.length;
int[] pointer = new int[m];
Arrays.fill(pointer, 1);
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int minNum = Integer.MAX_VALUE;
int minIndex = Integer.MAX_VALUE;
for (int j = 0; j < m; j++) {
int val = dp[pointer[j]] * primes[j];
// 去重
if (val == dp[i - 1]) {
pointer[j]++;
val = dp[pointer[j]] * primes[j];
}
if (minNum > val) {
minNum = val;
minIndex = j;
}
}
dp[i] = minNum;
pointer[minIndex]++;
}
return dp[n];
}
}
时间复杂度： O(n*m)
，两层循环分别是n次和m次。空间复杂度： O(n+m)
，dp数组大小为n，pointer数组大小为m。
运行结果如下：
方法三、动态规划 + 堆
上面我们使用一个pointer数组来记录每个primes中的数被乘了几次，其实，我们也可以使用堆来存储将要弹出的丑数，我们称为候选丑数，每次弹出一个丑数的时候我们其实可以计算得到下次的x的倍数的丑数为多少，其中x为primes数组中的数。
我们还是以primes = [2,7,13,19]
为例，dp作为结果集，下标从1开始：
第一个元素恒定为1，即 dp[1] = 1
，先将primes中所有元素入堆，并记录他们对应到dp的下标都是1弹出堆顶元素，即2，为第二个丑数，记为 dp[2]=2
，在弹出2的同时，我们可以计算得到下一个2的倍数的丑数为2*dp[1+1]=2*dp[2]=4（++1为之前的下标1+1）
，我们将这个4入堆，它的索引为2弹出堆顶元素，即4，为第三个丑数，记为 dp[3]=4
，在弹出4的同时，我们可以计算得到下一个2的倍数的丑数为2*dp[2+1]=2*dp[3]=8
，我们将这个8入堆，它的索引为3弹出堆顶元素，即7，为第四个丑数，记为 dp[4]=7
，在弹出7的同时，我们可以计算得到下一个7的倍数的丑数为7*dp[1+1]=7*dp[2]=14
，我们将这个14入堆，它的索引为2弹出堆顶元素，即8，为第五个丑数，记为 dp[5=8]
，在弹出8的同时，我们可以计算得到下一个2的倍数的丑数为2*dp[3+1]=2*dp[4]=14
，我们将这个14入堆，它的索引为4，可以看到，这个14重复了，后面要去重
依次类推，代码如下：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
if (n == 1) {
return 1;
}
PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
for (int i = 0; i < primes.length; i++) {
// 三个值分别为候选丑数、下标、索引
// 索引每使用一次就加1
heap.offer(new int[] {primes[i], i, 1});
}
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int[] element = heap.poll();
while (element[0] == dp[i - 1]) {
element[2]++;
element[0] = dp[element[2]] * primes[element[1]];
heap.offer(element);
element = heap.poll();
}
dp[i] = element[0];
element[2]++;
heap.offer(new int[] {dp[element[2]] * primes[element[1]], element[1], element[2]});
}
return dp[n];
}
}
时间复杂度： O(n*logm)
，对于每一个丑数，都要对堆做一次弹出操作和一次入堆操作。空间复杂度： O(n+m)
，dp数组大小为n，堆大小为m。
运行结果如下，可以看到，虽然时间复杂度减小了，但是运行时间却增加了，跟测试用例也有很大的关系。
最后
如果对你有帮助，请点个赞吧，谢谢^^
也可以关注我的公号【彤哥来刷题啦】，每日分享题解，一起刷题，一起拿全家桶。
点击“阅读原文”可以直达leetcode题解，电脑端看更方便。
