This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic describes

This is 313 on LeetCode. Super ugly, medium difficulty.

Tag: Priority queue, Multipath Merge

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

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

The title data guarantees that the NTH super ugly number is in the 32-bit signed integer range.

Example 1:

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

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].Copy the code

Tip:

  • 1 <= n <=
    1 0 6 10^6
  • 1 <= primes.length <= 100
  • 2 <= primes[i] <= 1000
  • Primes [I] is a prime number
  • All values in primes are distinct and in ascending order

Fundamental analysis

A similar question appeared in the previous Daily question.

264. Ugly number II

According to the definition of an ugly number, we can conclude:

  • 111 is the least ugly number.
  • If an ugly number XXX is multiplied by any given prime factor primes[I]primes[I]primes[I], the result is still ugly.

Priority queue (heap)

With the basic analysis in mind, a simple solution is to use a priority queue:

  1. Start by putting the maximum number of clowns 111 into the queue
  2. The minimum value XXX is fetched from the queue each time, and then the ugly number x∗primes[I]x * primes[I]x∗primes[I] corresponding to XXX is entered into the queue.
  3. Loop through step 222 many times, and the NNN outbound value is the answer.

To prevent the same ugly number from being queued more than once, we need to use the data structure SetSetSet to record the ugly number that has been queued.

Code:

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> q = new PriorityQueue<>();
        q.add(1L);
        set.add(1L);
        while (n-- > 0) {
            long x = q.poll();
            if (n == 0) return (int)x;
            for (int k : primes) {
                if(! set.contains(k * x)) { set.add(k * x); q.add(k * x); }}}return -1; // never}}Copy the code
  • Time complexity: If the length of PrimesPrimesPrimes is MMM, NNN elements should be ejected from the priority queue (heap), at most MMM elements should be put in each eject, and at most N ∗ Mn * MN ∗ M elements should be put in the heap. The complexity of O (n ∗ mlog ⁡ n ∗ (m)) O (n * m \ log {(n * m)}) O (n ∗ mlog n ∗ (m))
  • Space complexity: O(n∗m)O(n * m)O(n∗m)

Multi-channel merge

From solution 1, it is not difficult to find that our “subsequent ugly numbers” are based on “existing ugly numbers” (use “existing ugly numbers” multiplied by “given prime factors” primes[I]primes[I]primes[I]).

So, if our ordered sequence of all the ugly numbers is A1, A2,a3… ,ana1,a2,a3,… ,ana1,a2,a3,… If,an, each number in the sequence must be covered by at least one of the following three sequences (here assuming primes=[2,3,5]primes =[2,3,5]primes =[2,3,5]) :

  • The ordered sequence from the hideous number * 222 is: 1∗21 * 21∗2, 2∗22 * 22∗2, 3∗23 * 23∗2, 4∗24 * 24∗2, 5∗25 * 25∗2, 6∗26 * 26∗2, 8∗28 * 28∗2…
  • The ordered sequence from the hideous number * 333 is: 1∗31 * 31∗3, 2∗32 * 32∗3, 3∗33 * 33∗3, 4∗34 * 34∗3, 5∗35 * 35∗3, 6∗36 * 36∗3, 8∗38 * 38∗3…
  • The ordered sequence derived from the number * 555 is: 1∗51 * 51∗5, 2∗52 * 52∗5, 3∗53 * 53∗5, 4∗54 * 54∗5, 5∗55 * 55∗5, 6∗56 * 56∗5, 8∗58 * 58∗5…

We make these ordered sequences arrarrarr, and the final ugly sequence ansansans.

If the length of primesprimesprimes is MMM, we can use the MMM pointer to point to the current subscript of the arrarrarr sequence in MMM.

Obviously, we need to take the smallest value in MMM each time, then move the pointer backward (putting the next value in the current sequence into the heap), and repeat the process until we find the NNN ugly number.

Of course, to implement, we don’t need to construct this ordered sequence.

(val, I,idx)(val, I,idx)(val, I,idx)(val, I,idx)

  • Valvalval: the current list pointer points to a specific value;
  • Iii: this is an ordered sequence constructed by primes[I]primes[I]primes[I];
  • Val =ans[idx]∗primes[I]val=ans[idx] * primes[I]val=ans[idx]∗primes[I]val=ans[idx]∗primes[I].

To start, we add all (primes[I], I,0)(primes[I], I,0)(primes[I], I,0) to the priority queue (heap), fetching the smallest element from the heap at a time, Then the next element to be put in is (ans[idx+1]∗primes[I], I,idx+1)(ans[idx +1] * primes[I], I,idx+1)(ans[idx +1]∗primes[I], I,idx+1).

In addition, since the pointer movement of each of our ArrarrarR and the construction of Ansansans are monotonically increasing, we can achieve the deweighting by comparing with the current last bit construction of ans[x]ans[x]ans[x] ans[x] without referring to the Set structure with a large constant.

Code:

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int m = primes.length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]); 
        for (int i = 0; i < m; i++) {
            q.add(new int[]{primes[i], i, 0});
        }
        int[] ans = new int[n];
        ans[0] = 1;
        for (int j = 1; j < n; ) {
            int[] poll = q.poll();
            int val = poll[0], i = poll[1], idx = poll[2];
            if(val ! = ans[j -1]) ans[j++] = val;
            q.add(new int[]{ans[idx + 1] * primes[i], i, idx + 1});
        }
        return ans[n - 1]; }}Copy the code
  • Time complexity: need to construct the answer of length NNN, each construct needs to pull and put elements into the heap, there are MMM elements in the heap, at the beginning, need to traverse the primesprimesprimes, complexity O(m)O(m)O(m). The overall complexity of O (Max ⁡ (m, nlog ⁡ m)) O (\ Max (m, n \ log {m})) O (Max (m, nlogm))
  • Space complexity: store NNN answers, have MMM elements in the heap, complexity is O(n+m)O(n +m)O(n +m)

The last

This is the number 313 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour…

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.