313. Super Ugly Number

1. Question

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.

2. Examples

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].

3. 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.

4. References

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/super-ugly-number 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

5. Solutions

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        HashSet<Long> added = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        added.add(1L);
        queue.offer(1L);
        int ugly = 0;

        for (int i = 0; i < n; i++) {
            Long curr = queue.poll();
            ugly = Math.toIntExact(curr);
            for (int prime : primes) {
                long next = curr * prime;
                if (added.add(next)) {
                    queue.offer(next);
                }
            }

        }
        return ugly;
    }
}
Copyright © rootwhois.cn 2021-2022 all right reserved,powered by GitbookFile Modify: 2022-11-26 20:03:31

results matching ""

    No results matching ""