313 Super Ugly Number

1. Question

Write a program to find the nthsuper ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime listprimesof sizek. For example,[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]is the sequence of the first 12 super ugly numbers givenprimes=[2, 7, 13, 19]of size 4.
Note: (1)1is a super ugly number for any givenprimes. (2) The given numbers inprimesare in ascending order. (3) 0 <k≤ 100, 0 <n≤ 106, 0 <primes[i]< 1000. (4) The nthsuper ugly number is guaranteed to fit in a 32-bit signed integer.

2. Implementation

(1) Heap
1
class Solution {
2
public int nthSuperUglyNumber(int n, int[] primes) {
3
if (primes == null || primes.length == 0) {
4
return 0;
5
}
6
7
PriorityQueue<Long> minHeap = new PriorityQueue<>();
8
minHeap.add(1L);
9
10
long curNum = 1;
11
12
for (int i = 1; i <= n; i++) {
13
curNum = minHeap.remove();
14
15
while (!minHeap.isEmpty() && minHeap.peek() == curNum) {
16
minHeap.remove();
17
}
18
19
for (int prime : primes) {
20
minHeap.add(curNum * prime);
21
}
22
}
23
return (int)curNum;
24
}
25
}
Copied!

3. Time & Space Complexity

Heap:时间复杂度O(mn * logmn), 空间复杂度O(mn)