超级丑数
难度:
标签:
题目描述
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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 <= 1051 <= primes.length <= 1002 <= primes[i] <= 1000- 题目数据 保证
primes[i]是一个质数 primes中的所有值都 互不相同 ，且按 递增顺序 排列
代码结果
运行时间: 140 ms, 内存: 21.9 MB
/*
思路：
使用最小堆来生成超级丑数。我们将初始丑数1放入堆中，然后不断从堆中取出最小的元素，
用给定的质数数组中的质数进行乘积，再将结果放入堆中，确保没有重复的元素。重复这一过程，直到得到第n个超级丑数。
使用Java Stream实现代码。
*/
import java.util.*;
import java.util.stream.*;
public class SuperUglyNumberStream {
public int nthSuperUglyNumber(int n, int[] primes) {
PriorityQueue<Long> heap = new PriorityQueue<>();
Set<Long> seen = new HashSet<>();
heap.add(1L);
seen.add(1L);
long ugly = 1L;
for (int i = 0; i < n; i++) {
ugly = heap.poll();
for (int prime : primes) {
long next = ugly * prime;
if (seen.add(next)) {
heap.add(next);
}
}
}
return (int) ugly;
}
public static void main(String[] args) {
SuperUglyNumberStream solution = new SuperUglyNumberStream();
int n = 12;
int[] primes = {2, 7, 13, 19};
System.out.println(solution.nthSuperUglyNumber(n, primes)); // 输出32
}
}解释
方法:
这个题解使用了最小堆来解决超级丑数问题。具体思路如下：
1. 初始化一个结果数组 ans，并将 1 作为第一个超级丑数加入 ans。
2. 使用一个最小堆 pq 存储 (prime, idx) 元组，其中 prime 表示质数，idx 表示该质数在 primes 数组中的下标。最小堆按照 prime 值进行排序。
3. 初始化一个数组 primes_idx，用于记录每个质数在 ans 数组中的下标。
4. 循环 n-1 次，每次从最小堆中取出最小的 (prime, idx) 元组，将 prime 加入 ans 数组。
5. 更新 primes_idx[idx]，找到下一个未被使用的 ans[primes_idx[idx]]，将其与当前质数相乘，得到新的超级丑数，并将其加入最小堆中。
6. 最终返回 ans 数组的最后一个元素，即第 n 个超级丑数。
时间复杂度:
O(n * log k)，其中 n 是要求的超级丑数的编号，k 是质数数组的长度。
空间复杂度:
O(n + k)，其中 n 是要求的超级丑数的编号，k 是质数数组的长度。
代码细节讲解
🦆
为什么选择使用最小堆来解这道超级丑数的问题？
▷🦆
在算法中，如果在最小堆中存在重复的超级丑数，是否会影响最终结果或效率？
▷🦆
算法中提到的`更新 primes_idx[idx]`步骤中，为什么要寻找下一个未被使用的ans[primes_idx[idx]]，这样做的目的是什么？
▷🦆
代码实现中提到将每个质数与ans数组中的对应元素相乘，这里的对应元素是如何选择的？
▷