超级丑数
-
题目
写一个程序来找第 n 个超级丑数。
超级丑数的定义是正整数并且所有的质数因子都在所给定的一个大小为 k 的质数集合内。比如给你 4 个质数的集合 [2, 7, 13, 19], 那么 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是前 12 个超级丑数。注意事项
1 永远都是超级丑数不管给的质数集合是什么。
给你的质数集合已经按照升序排列。
0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000 -
样例
给出 n = 6 和质数集合 [2, 7, 13, 19]。第 6 个超级丑数为 13，所以返回 13 作为结果。
-
题解
思路与4.Ugly Number II-丑数 II（中等题）是一样的，需要用一个队列数组来保存质数集合中的所有元素。
public class Solution {/*** @param n a positive integer* @param primes the given prime list* @return the nth super ugly number*/public int nthSuperUglyNumber(int n, int[] primes) {int len = primes.length;Queue[] queueArr = new Queue[len];int count = 1;int val = 1;for (int i=0;i<len;i++){queueArr[i] = new LinkedList<Integer>();}while (count < n){for (int i=0;i<len;i++){queueArr[i].offer(primes[i]*val);}int min = (Integer)queueArr[0].peek();for (int i=1;i<len;i++){if ((Integer)queueArr[i].peek() < min){min = (Integer)queueArr[i].peek();}}for (int i=0;i<len;i++){if ((Integer)queueArr[i].peek() == min){queueArr[i].poll();}}count++;val = min;}return val;}}Last Update 2016.12.4