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 first10
ugly numbers.
Note:
1
is typically treated as an ugly number.n
does not exceed 1690.
Hint:
- The naive approach is to call
isUgly
for every number until you reach the n one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones. - An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
- The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L, L, and L.
- Assume you have U, the k ugly number. Then U must be Min(L * 2, L * 3, L * 5).
这道题是之前那道 Ugly Number 的拓展,这里让找到第n个丑陋数,还好题目中给了很多提示,基本上相当于告诉我们解法了,根据提示中的信息,丑陋数序列可以拆分为下面3个子列表:
(1) 1x2, 2x2, 2x2, 3x2, 3x2, 4x2, 5x2...
(2) 1x3, 1x3, 2x3, 2x3, 2x3, 3x3, 3x3...
(3) 1x5, 1x5, 1x5, 1x5, 2x5, 2x5, 2x5...
仔细观察上述三个列表,可以发现每个子列表都是一个丑陋数分别乘以 2,3,5,而要求的丑陋数就是从已经生成的序列中取出来的,每次都从三个列表中取出当前最小的那个加入序列,请参见代码如下:
解法一:
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> res(, );
int i2 = , i3 = , i5 = ;
while (res.size() < n) {
int m2 = res[i2] * , m3 = res[i3] * , m5 = res[i5] * ;
int mn = min(m2, min(m3, m5));
if (mn == m2) ++i2;
if (mn == m3) ++i3;
if (mn == m5) ++i5;
res.push_back(mn);
}
return res.back();
}
};
我们也可以使用最小堆来做,首先放进去一个1,然后从1遍历到n,每次取出堆顶元素,为了确保没有重复数字,进行一次 while 循环,将此时和堆顶元素相同的都取出来,然后分别将这个取出的数字乘以 2,3,5,并分别加入最小堆。这样最终 for 循环退出后,堆顶元素就是所求的第n个丑陋数,参见代码如下:
解法二:
class Solution {
public:
int nthUglyNumber(int n) {
priority_queue<long, vector<long>, greater<long>> pq;
pq.push();
for (long i = ; i < n; ++i) {
long t = pq.top(); pq.pop();
while (!pq.empty() && pq.top() == t) {
t = pq.top(); pq.pop();
}
pq.push(t * );
pq.push(t * );
pq.push(t * );
}
return pq.top();
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/264
类似题目:
参考资料:
https://leetcode.com/problems/ugly-number-ii/
https://leetcode.com/problems/ugly-number-ii/discuss/69372/Java-solution-using-PriorityQueue