超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 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] 中。
提示:
链接: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[]
表示结果:
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开始:
dp[1] = 1
,先将primes中所有元素入堆,并记录他们对应到dp的下标都是1dp[2]=2
,在弹出2的同时,我们可以计算得到下一个2的倍数的丑数为 2*dp[1+1]=2*dp[2]=4(++1为之前的下标1+1)
,我们将这个4入堆,它的索引为2dp[3]=4
,在弹出4的同时,我们可以计算得到下一个2的倍数的丑数为2*dp[2+1]=2*dp[3]=8
,我们将这个8入堆,它的索引为3dp[4]=7
,在弹出7的同时,我们可以计算得到下一个7的倍数的丑数为7*dp[1+1]=7*dp[2]=14
,我们将这个14入堆,它的索引为2dp[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