### LeetCode  • ㊗️
• 大家
• offer
• 多多！

## Problem

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 $n^{th}$ super ugly number.

The $n^{th}$ 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 <= 10^5$
• $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.

## Code

class Solution {
class Num {
int val;
int index;
int prime;

public Num (int val, int index, int prime){
this.val = val;
this.index = index;
this.prime = prime;
}
}

public int nthSuperUglyNumber(int n, int[] primes) {
int[] res = new int[n];
res = 1;

PriorityQueue<Num> queue = new PriorityQueue<>((a, b) -> (a.val - b.val));
for(int i = 0; i < primes.length; i++){
queue.offer(new Num(primes[i], 1, primes[i]));
}

for(int i = 1; i < n; i++){
res[i] = queue.peek().val;
while(queue.peek().val == res[i]){
Num curr = queue.poll();
queue.offer(new Num(curr.prime * res[curr.index], curr.index + 1, curr.prime));
}
}

return res[n - 1];
}
}

class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
dp = defaultdict(int)
res =  * n
res = 1

for i in range(1, n):
m = float("inf")
for prime in primes:
m = min(m, res[dp[prime]] * prime)

for prime in primes:
if res[dp[prime]] * prime == m:
dp[prime] += 1

res[i] = m

return res[n - 1]