Leetcode super ugly number

Title Description

The super ugly number is a positive integer, and all its prime factors appear in the prime array primes. Give you an integer n and an integer array primes to return the nth super ugly number. The title data ensures that the nth super ugly number is within the range of 32-bit signed integers.

Example 1:

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

Example 2:

Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 does not contain prime factors, so all its prime factors are in the prime array primes = [2,3,5].

1, Minimum heap

/**
* @Description: Minimum heap implementation
* @Param: [n, primes]
* @return: int
* @Author: xiaobao
* @Date: 2021/8/9
*/
    public int nthSuperUglyNumber1(int n, int[] primes) {
        Set<Long> ans=new HashSet<>();
        ans.add(1L);
        PriorityQueue<Long> heap=new PriorityQueue<>();
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();
            ugly = (int) curr;
            for (int prime : primes) {
                long next = curr * prime;
                if (ans.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }

The method of minimum heap is used. The value at the top of the small root heap is the current ugly number every time. It can be obtained by cycling to n. since PriorityQueue is realized through binary small top heap, PriorityQueue is used in the program. However, because duplicate numbers may occur in the generation process, hashset needs to be used to remove them.

   /**
    * @Description: treeset realization
    * @Param: [n, primes]
    * @return: int
    * @Author: xiaobao
    * @Date: 2021/8/9
    */
    public int nthSuperUglyNumber(int n, int[] primes) {
        TreeSet<Long> ans=new TreeSet<>();
        ans.add(1L);
        for(int i=1;i<n;i++)
        {
            Long min=ans.pollFirst();
            for (int prime : primes) {
                ans.add(min*prime);
            }
        }
        return Math.toIntExact(ans.pollFirst());
    }

Because treeset can realize arrangement and weight reduction, treeset can be directly used to implement the code.

2, Dynamic programming

    /**
    * @Description: It is realized by dynamic programming method
    * @Param: [n, primes]
    * @return: int
    * @Author: xiaobao
    * @Date: 2021/8/9
    */
    public int nthSuperUglyNumber2(int n, int[] primes){
        int dp[]=new int[n+1];
        dp[1]=1;
        int len=primes.length;
        int pointers[]=new int[len];
        Arrays.fill(pointers,1);
        for(int i=2;i<=n;i++)
        {
            int nums[]=new int[len];
            int min= Integer.MAX_VALUE;
            for(int j=0;j<len;j++)
            {
                nums[j]=dp[pointers[j]]*primes[j];
                min=min>nums[j]?nums[j]:min;
            }
            dp[i]=min;
            for(int k=0;k<len;k++)
            {
                if(nums[k]==min)
                {
                    pointers[k]++;
                }
            }
        }
        return dp[n];

    }

See leetcode's official explanation for the illustrated tutorial https://leetcode-cn.com/problems/super-ugly-number/solution/chao-ji-chou-shu-by-leetcode-solution-uzff/
Explanation of schematic diagram of problem solution:
nums [] array is an array of ugly numbers corresponding to primes each time. The smallest one is the ugly number of current i until n is returned
The dp [] array stores the ugly number sequence. Each time, the smallest one is filtered out from the num array, and then placed in the corresponding position of the dp array
The pointers [] array actually corresponds to the primes array. The subscript represents different numbers in the prime array primes. The content represents the position of the dp number. It multiplies the value in the prime array primes pointed to by the corresponding subscript of the pointers array, and then selects the smallest bit from nums to update the dp content of the current bit. At the same time, it iterates through the nums array, If a value equal to min is encountered, the number in the corresponding pointer is++

summary

If the minimum heap is used, the corresponding space complexity is high, while the dynamic programming method has less space overhead. It only needs the size of the corresponding nums and pointers with the same prime array length, and the space complexity is low.