This is the 9th day of my participation in the August Wen Challenge.More challenges in August

313. Super ugly

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

Given an integer n and an integer array primes, return the NTH super ugly number.

The problem data guarantees that the NTH super ugly number is in the range of 32-bit signed integers.

  • Example 1:

Input: n = 12, primes = [2,7,13,19] output: 32 description: given a primes array of length 4, primes = [2,7,13,19], the first 12 super-ugly sequences are: ,2,4,7,8,13,14,16,19,26,28,32 [1].

  • Example 2:

Input: n = 1, primes = [2,3,5] output: 1 explanation: 1 has no prime factors, so all its prime factors are in the prime array primes = [2,3,5].

(Minimum heap)

Using the priority queue, generate the super ugly number one by one, so the NTH smallest ugly number generated is what we need

code

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {

        PriorityQueue<Long> priorityQueue=new PriorityQueue<>();
        priorityQueue.add(1L);
        Set<Long> set=new HashSet<>();
        set.add(1L);
        int i=0;
        while(! priorityQueue.isEmpty()) {long cur = priorityQueue.poll();
            if (++i==n)
                return (int) cur;
            for (int prime : primes) {
                if (set.contains(cur*prime))
                    continue; set.add(cur*prime); priorityQueue.add(cur*prime); }}return -1; }}Copy the code

(DP)

  1. Using dynamic programming, dp[I] represents the ith ugly number
  2. This is similar to ugly number two. We need to maintain a pointer to the p[I] ugly number for each prime number in the prime array. Because in the naive way, we need to multiply the ugly number by all the numbers in the prime array, so we maintain the pointer array to represent: The result of p[j]-1 ugly *primes[j] has been added to the dp array. Now it is p[j]-1 ugly *primes[j]

code

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {

        int[] dp = new int[n+1];
        int[] p=new int[primes.length];
        Arrays.fill(p,1);
        dp[1] =1;
        for (int i=2; i<=n; i++) {int min=Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++) {
                min= Math.min(min,primes[j]*dp[p[j]]);
            }
            dp[i]=min;
            for (int j = 0; j < primes.length; j++) {
                if(primes[j]*dp[p[j]]==min) { p[j]++; }}}returndp[n]; }}Copy the code