# 313    Super Ugly Number

## 313. [Super Ugly Number](https://leetcode.com/problems/super-ugly-number/description/)

## 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**

```java
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        if (primes == null || primes.length == 0) {
            return 0;
        }

        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        minHeap.add(1L);

        long curNum = 1;

        for (int i = 1; i <= n; i++) {
            curNum = minHeap.remove();

            while (!minHeap.isEmpty() && minHeap.peek() == curNum) {
                minHeap.remove();
            }

            for (int prime : primes) {
                minHeap.add(curNum * prime);
            }
        }
        return (int)curNum;
    }
}
```

## 3. Time & Space Complexity

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