超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 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^5$
$1 <= primes.length <= 100$
$2 <= primes[i] <= 1000$
题目数据 保证 primes[i] 是一个质数
primes 中的所有值都 互不相同 ，且按 递增顺序 排列
审题
超级丑数：质因数需在制定的primes数组中
丑数的primes数组是 2,3,5
输出超级丑数序列，找到第n个
1是即时丑数，也是超级丑数。
算法说明：
1、遍历所有自然数
2、判断当前自然数的质因数都在数组primes中
2.1 遍历整除判断
2.2 直到当前自然数变成了1
2.3 累加超级丑数的计数直到找到第n个
暴力实现
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
if (n == 1) {
return 1;
}
int count = 1;
for (int i = 2; i < Integer.MAX_VALUE; i++) {
int tmp = i;
for (int p : primes) {
while (tmp >= p && tmp % p == 0 && tmp / p >= 1 && tmp > 1) {
tmp = tmp / p;
}
}
if (tmp == 1) {
count++;
// System.out.println(i + " 是第" + count + "个超级丑数");
if (count == n) {
return i;
}
}
}
return -1;
}
}
问题：
- 会超时：时间复杂度分析O(nmk) m是prime数组的长度，k是数字质因数分解尝试的次数（成功或者失败）
动态规划
- 空间换时间
超级质数 本质上 是 质因数数组的幂次或者相互乘积的组合。
所以只需要累乘，找到第n个数字就行
需要：
1、维护一个从大到小的队列，存储超级丑数
2、遍历计算，求出第n个丑数，从队列取出返回
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
PriorityQueue<Integer> q = new PriorityQueue<>();
q.add(1);
while (n-- > 0) {
int x = q.poll();
if (n == 0) return x;
for (int k : primes) {
if (k <= Integer.MAX_VALUE / x) q.add(k * x);
if (x % k == 0) break;
}
}
return -1; // never
}
}
// 链接：https://leetcode.cn/problems/super-ugly-number/solutions/924673/gong-shui-san-xie-yi-ti-shuang-jie-you-x-jyow/
我们需要一个长度为n的数组，存储超级质数。
对于质因数数组的每一个元素，与其他元素乘积产生的超级丑数，称为一列丑数。
递增构造：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int m = primes.length;
// 设置排序比较器
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]);
for (int i = 0; i < m; i++) {
q.add(new int[]{primes[i], i, 0});
}
int[] ans = new int[n];
ans[0] = 1;
for (int j = 1; j < n; ) {
int[] poll = q.poll();
int val = poll[0], i = poll[1], idx = poll[2];
if (val != ans[j - 1]) ans[j++] = val;
// 自动排序
q.add(new int[]{ans[idx + 1] * primes[i], i, idx + 1});
}
return ans[n - 1];
}
}
// 链接：https://leetcode.cn/problems/super-ugly-number/solutions/924673/gong-shui-san-xie-yi-ti-shuang-jie-you-x-jyow/
标准动态规划
- 定义数组 dp，其中 dp[i] 表示第 i 个超级丑数，第 n 个超级丑数即为 dp[n]
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int[] dp = new int[n + 1];
int m = primes.length;
int[] pointers = new int[m];
int[] nums = new int[m];
Arrays.fill(nums, 1);
for (int i = 1; i <= n; i++) {
int minNum = Arrays.stream(nums).min().getAsInt();
dp[i] = minNum;
for (int j = 0; j < m; j++) {
if (nums[j] == minNum) {
pointers[j]++;
nums[j] = dp[pointers[j]] * primes[j];
}
}
}
return dp[n];
}
}
// 链接：https://leetcode.cn/problems/super-ugly-number/solutions/924207/chao-ji-chou-shu-by-leetcode-solution-uzff/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
