313 Super Ugly Number

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

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)