Super Ugly Number 518
Question
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Notice
1 is a super ugly number for any given primes.
The given numbers in primes are in ascending order.
0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000
Example
Given n = 6, primes = [2, 7, 13, 19] return 13
Solution
用HashMap + PriorityQueue。取n－1次最小堆堆顶元素，最后堆顶元素为第n个prime。
代码如下：
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) {
// Write your code here
if(primes == null || primes.length == 0 || n <= 0){
return 0;
}
Queue<Long> Q = new PriorityQueue<Long>();
HashSet<Long> inQ = new HashSet<Long>();
Q.add(Long.valueOf(1));
inQ.add(Long.valueOf(1));
for(int i = 1; i < n; i++){
Long curt = Q.poll();
for(int j = 0; j < primes.length; j++){
Long next = curt * primes[j];
if(!inQ.contains(next)){
Q.add(next);
inQ.add(next);
}
}
}
return Q.peek().intValue();
}
}