0313. Super Ugly Number

https://leetcode.com/problems/super-ugly-number

Description

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Example 1:

**Input:** n = 12, primes = [2,7,13,19]
**Output:** 32
**Explanation:** [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].

Example 2:

**Input:** n = 1, primes = [2,3,5]
**Output:** 1
**Explanation:** 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

Constraints:

• 1 <= n <= 106

• 1 <= primes.length <= 100

• 2 <= primes[i] <= 1000

• primes[i] is guaranteed to be a prime number.

• All the values of primes are unique and sorted in ascending order.

ac

https://leetcode.com/problems/super-ugly-number/discuss/277313/My-view-of-this-question-hope-it-can-help-you-understand!!!

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        PriorityQueue<int[]> queue=new PriorityQueue<>((a,b)->(a[0]-b[0]));
        for (int i=0;i<primes.length;i++)
            queue.offer(new int[]{primes[i], primes[i], 0});

        int[] nums=new int[n+1];
        nums[0]=1;

        int i=1;
        while (i<n){
            int[] entry=queue.poll();
            int num=entry[0], prime=entry[1], index=entry[2];
            // remove duplicate
            if (num!=nums[i-1]){
                nums[i]=num;
                i++;
            }
            queue.offer(new int[]{prime*nums[index+1], prime, index+1});
        }
        return nums[n-1];
    }
}