LeetCode 264 - Ugly Number II

作者 QIFAN 日期 2016-12-21
LeetCode 264 - Ugly Number II

原题链接:264. Ugly Number II


题目

找到第 n 个 ugly number。
ugly number 指素数因子除了 1 和本身只有 2,3,5 的数。
1 是第一个 ugly number。

思路

思路 1 Brute Force

简单粗暴的想到,从 1 开始遍历正整数判断其是否“丑”,直到找到第 n 个。但是这样需要的时间比较长。Can we do better?

思路 2 Priority Queue

首先注意到,假设有一个 ugly number n,它可以“扩展”为 3 个新的 ugly number :2*n,3*n,5*n
加入有前 k 个 ugly number,则下一个 ugly number 肯定是从这 k 个 ugly number “扩展”开的新数中产生,即最小的那一个。
因此,只要每次找到前 k 个 ugly number 扩展出的最小数。

为了节省计算,使用 PriorityQueue 存储历史扩展数,每次只需计算第 k 个数的扩展放入队列。

坑 1 :重复数据。PriorityQueue 中允许重复,而 ugly number 是不会重复的,而且是严格递增的。所以直到最小的队列中的数小于前一个 ugly number,才将其插入。
坑 2 :integer overflow。LeetCode 桑心病狂的把数字弄到了一亿,所以就把 int 变成了 long 。

代码:

public class Solution {
public int nthUglyNumber(int n) {
PriorityQueue<Long> buffer = new PriorityQueue<>();
long[] uglyNum = new long[n];
uglyNum[0] = 1;
int currPos = 0;
while (currPos < n - 1) {
buffer.add(2 * uglyNum[currPos]);
buffer.add(3 * uglyNum[currPos]);
buffer.add(5 * uglyNum[currPos]);
long candidate = buffer.poll();
while (candidate <= uglyNum[currPos]) {
candidate = buffer.poll();
}
uglyNum[++currPos] = candidate;
}
return (int)uglyNum[n - 1];
}
}