264. Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

Solution

Approach 1: Three queues.

Approach 2: Minumum heap.

Code (Python)

Approach 1:

Approach 2:

Code (C++)

Approach 1:

// Three queues.
class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 0)
            return 0;
        queue<long> q2;
        queue<long> q3;
        queue<long> q5;
        long res = 1;
        for (int i = 2; i <= n; ++i)
        {
            q2.push(res * 2);
            q3.push(res * 3);
            q5.push(res * 5);
            res = std::min(std::min(q2.front(), q3.front()), q5.front());
            if (q2.front() == res)
                q2.pop();
            if (q3.front() == res)
                q3.pop();
            if (q5.front() == res)
                q5.pop();
        }
        return res;
    }
};

Approach 2:

// Minumum heap.
class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 0)
            return 0;
        priority_queue<long, vector<long>, greater<long>> minHeap;
        minHeap.push(1);
        long res = 1;
        for (int i = 2; i <= n; ++i)
        {
            while (!minHeap.empty() && minHeap.top() == res)
                minHeap.pop();
            minHeap.push(res * 2);
            minHeap.push(res * 3);
            minHeap.push(res * 5);
            res = minHeap.top();
        }
        return res;
    }
};