Title Description

This is "264. Ugly number II" on LeetCode, and the difficulty is "medium".

Tag: "multiway merge", "heap", "priority queue"

Give you an integer n, please find out and return the nth ugly number.

Ugly numbers are positive integers that contain only prime factors 2, 3, and 5.

Example 1:

Input: n = 10

Output: 12

Explanation:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] Is a sequence of the first 10 ugly numbers.

Example 2:

Input: n = 1

Output: 1

Explanation: 1 is usually regarded as an ugly number.

Tips:

• 1 <= n <= 1690

Basic ideas

According to the definition of ugly number, we have the following conclusions:

• 1 is the smallest ugly number.
• For any ugly number x, it is multiplied by any prime factor (2, 3, 5), and the result (2x, 3x, 5x) is still an ugly number.

Priority queue (small root heap)

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

1. First put the minimum ugly number 1 into the queue
2. Take out the minimum value x from the queue each time, and then queue the ugly numbers 2x, 3x and 5x corresponding to X.
3. Repeat step 2 for many times, and the value of the nth time out of the queue is the answer.

In order to prevent the same ugly number from entering the queue multiple times, we need to use the data structure Set to record the ugly numbers that have entered the queue.

code:

class Solution {
    int[] nums = new int[]{2,3,5};
    public int nthUglyNumber(int n) {
        Set<Long> set = new HashSet<>();
        Queue<Long> pq = new PriorityQueue<>();
        set.add(1L);
        pq.add(1L);
        for (int i = 1; i <= n; i++) {
            long x = pq.poll();
            if (i == n) return (int)x;
            for (int num : nums) {
                long t = num * x;
                if (!set.contains(t)) {
                    set.add(t);
                    pq.add(t);
                }
            }
        }
        return -1;
    }
}

• Time complexity: the minimum value taken from the priority queue is O(1), and the complexity of adding elements to the priority queue is O(\log{n}). The overall complexity is O(n\log{n})
• Space complexity: O(n)

Multiway merge (multi pointer)

From solution 1, it is not difficult to find that our "future ugly numbers" are based on "existing ugly numbers" (using "existing ugly numbers" multiplied by "quality factors" 2, 3 and 5).

Therefore, if the ordered sequence of all our ugly numbers is A1, A2, A3, An, every number in the sequence must be covered by at least one of the following three sequences:

• The ordered sequence obtained from ugly number * 2: 1 * 2, 2 * 2, 3 * 2, 4 * 2, 5 * 2, 6 * 2, 6 * 2
• The ordered sequence obtained from ugly number * 3: 1 * 3, 2 * 3, 3 * 3, 4 * 3, 5 * 3, 6 * 3, 8 * 3
• The ordered sequence obtained from ugly number * 5: 1 * 5, 2 * 5, 3 * 5, 4 * 5, 5 * 5, 6 * 5, 8 * 5

For example 🌰， Suppose we need to find the last bit of [1, 2, 3,..., 10, 12] ugly number sequence arr, then the sequence can be regarded as the merging of the following three ordered sequences:

• 1 * 2, 2 * 2, 3 * 2, ... , 10 * 2, 12 * 2, put forward 2, that is, arr * 2
• 1 * 3, 2 * 3, 3 * 3, ... , 10 * 3, 12 * 3, put forward 3, that is, arr * 3
• 1 * 5, 2 * 5, 3 * 5, ... , 10 * 5, 12 * 5, put forward 5, that is, arr * 5. Therefore, we can use three pointers to point to a subscript of the target sequence arr (subscript 0 is not used as a sentry, and the start is 1), use arr [subscript] * prime factor to represent which bit of the three ordered sequences is currently used, and use idx to represent which ugly number of arr is currently generated.

code:

class Solution {
    public int nthUglyNumber(int n) {
        // ans is used to store the existing ugly number (starting from subscript 1, the first ugly number is 1)
        int[] ans = new int[n + 1];
        ans[1] = 1;
        // Because the three ordered sequences are all derived from the "existing ugly number" * "prime factor"
        // i2, i3 and i5 respectively represent which subscript of "existing ugly number" is currently used in the three ordered sequences (starting with 1)
        for (int i2 = 1, i3 = 1, i5 = 1, idx = 2; idx <= n; idx++) {
            // From ans[iX] * X, we can get which bit the current ordered sequence points to
            int a = ans[i2] * 2, b = ans[i3] * 3, c = ans[i5] * 5;
            // Store the smallest bit of the three ordered sequences into the "existing ugly number" sequence and move its subscript back
            int min = Math.min(a, Math.min(b, c));
            // Since the same ugly number may be generated between different ordered sequences, as long as the same ugly number is skipped (else if cannot be used)
            if (min == a) i2++; 
            if (min == b) i3++;
            if (min == c) i5++;
            ans[idx] = min;
        }
        return ans[n];
    }
}

• Time complexity: O(n)
• Space complexity: O(n)

last

This is the No.264 article of our "brush through LeetCode" series. The series began on January 1, 2021. As of the starting date, there are 1916 questions on LeetCode, some of which are locked questions. We will finish all the questions without locks first.

In this series of articles, in addition to explaining the problem-solving ideas, we will also give the most concise code as far as possible. If the general explanation is involved, the corresponding code template will also be.

In order to facilitate you to debug and submit code on the computer, I have established a relevant warehouse: https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address, you can see the problem solution link of the series of articles, the corresponding code of the series of articles, the original problem link of LeetCode and other preferred problem solutions.