# 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 is typically treated as an ugly number.
- 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;
}
};