中联汇科 网站建设,株洲芦淞区,企业文化墙设计图,石家庄百度搜索引擎优化超级丑数 是一个正整数#xff0c;并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes #xff0c;返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
示例 1#xff1a;
输入#xff1a;n 12,…超级丑数 是一个正整数并满足其所有质因数都出现在质数数组 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] 中。
解题思路最小堆
使用优先队列逐个生成超级丑数那么生成的第n小的丑数就是我们需要的
代码
class Solution {public int nthSuperUglyNumber(int n, int[] primes) {PriorityQueueLong priorityQueuenew PriorityQueue();priorityQueue.add(1L);SetLong setnew HashSet();set.add(1L);int i0;while (!priorityQueue.isEmpty()){long cur priorityQueue.poll();if (in)return (int) cur;for (int prime : primes) {if (set.contains(cur*prime))continue;set.add(cur*prime);priorityQueue.add(cur*prime);}}return -1;}
}解题思路dp
使用动态规划dp[i]代表第i个丑数这题类似与丑数二我们需要对质数数组中的每个质数维护一个指针指向第p[i]个丑数因为在朴素的做法中需要对丑数乘以所有质数数组中的数字所以我们维护的指针数组作用就是表示第p[j]-1个丑数*primes[j]的结果已经加入dp数组了现在需要加入dp数组的是p[j]个丑数 * primes[j]
代码
class Solution {public int nthSuperUglyNumber(int n, int[] primes) {int[] dp new int[n1];int[] pnew int[primes.length];Arrays.fill(p,1);dp[1]1;for (int i2;in;i){int minInteger.MAX_VALUE;for (int j 0; j primes.length; j) {min Math.min(min,primes[j]*dp[p[j]]);}dp[i]min;for (int j 0; j primes.length; j) {if(primes[j]*dp[p[j]]min){p[j];}}}return dp[n];}
}
