313. Super Ugly Number

JIAKAOBO

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[0] = 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 = [0] * n
        res[0] = 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]