My easy understanding Java solution, with PriorityQueue


  • 1
    D
    public int nthSuperUglyNumber(int n, int[] primes) {
            if (n == 1) {
                return 1;
            }
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            for (int x : primes) {
                pq.offer(x);
            }
            for (int i=0; i<n-2; ++i) {
                int cur = pq.poll();
                for (int x : primes) {  //each one pop out should multiply the array
                    long mult = (long)cur * (long)x;
                    if (mult < Integer.MAX_VALUE) {
                        pq.offer((int)mult);
                    }
                }
                while (pq.peek() == cur) {  // It is sorted, so if duplicate, only happen at root, poll it
                    pq.poll();
                }
            }
            return pq.poll();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.