313. Super Ugly Number

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.

Analysis:

Approach 1:

Use heap. Always poll from minheap and multiply with all primes and add them to minheap. Use a hashSet to put all numbers calculated so far to avoid duplication.

Approach 2:

"k pointers", use a array a[i] to keep track prime number should multiply which numbers in result array. Every loop, we scan through all prime numbers, to find out which one has the smallest multiply result, then we increment its a[i], and add the result into result arrray. This way we always adding smallest number to array.

Code for Approach #1: (Can't pass leetcode judge, time limit exceeded at 81/83 test case)

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        PriorityQueue<Integer> minheap = new PriorityQueue<Integer>(10, new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b)
            {
                return a.compareTo(b);
            }
        });

        Set<Integer> set = new HashSet<Integer>();

        minheap.offer(1);
        set.add(1);

        int nth = 0;

        for(int i=0; i<n-1; i++)
        {
            nth = minheap.poll();
            for(int j=0; j<primes.length; j++)
            {
                int temp = nth*primes[j];
                if(!set.contains(temp)){
                    minheap.offer(temp);
                    set.add(temp);
                }
            }
        }
        return minheap.peek();
    }
}