【每日一题】313. 超级丑数：一题三解：堆 & 动态规划 & 双剑合璧！
【每日一题】313. 超级丑数：一题三解：堆 & 动态规划 & 双剑合璧！
题目描述
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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`个。
运行结果：
image-20210809102303274
方法二、动态规划
通过观察可以看到，后面的丑数都是通过前面的丑数乘以一个倍数得来的，这个倍数一开始是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。
运行结果如下：
image-20210809151017668
方法三、动态规划 + 堆
上面我们使用一个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。
运行结果如下，可以看到，虽然时间复杂度减小了，但是运行时间却增加了，跟测试用例也有很大的关系。
image-20210809154158584