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 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.
Note: (1)`1`is a super ugly number for any given`primes`. (2) The given numbers in`primes`are 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
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
21
}
22
}
23
return (int)curNum;
24
}
25
}
Copied!

# 3. Time & Space Complexity

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