题目:
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
1
2
3
| 输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
|
方法一：最小堆
要得到从小到大的第 n 个丑数，可以使用最小堆实现。
初始时堆为空。首先将最小的丑数 1 加入堆。
每次取出堆顶元素 x，则 x 是堆中最小的丑数，由于 2x, 3x, 5x 也是丑数，因此将 2x, 3x, 5x 加入堆。
上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。
在排除重复元素的情况下，第 n 次从最小堆中取出的元素即为第 n 个丑数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public long nthUglyNumber2(int n) {
int[] factors = {2, 3, 5};
Set<Long> set = new HashSet<Long>();
PriorityQueue<Long> heap = new PriorityQueue<Long>();
set.add(1L);
heap.offer(1L);
long ugly = 0;
for (int i = 0; i < n; i++) {
ugly = heap.poll();
for (int factor : factors) {
long next = ugly * factor;
if (set.add(next)) {
heap.offer(next);
}
}
}
return ugly;
}
|
复杂度分析
- 时间复杂度：O(Nlog N)。得到第 n 个丑数需要进行 n 次循环，每次循环都要从最小堆中取出 1 个元素以及向最小堆中加入最多 3 个元素，时间复杂度是 C*O(log N)，总的时间复杂度是 O(Nlog N)。
- 空间复杂度：O(N)。主要取决于最小堆和哈希集合的大小，最小堆和哈希集合的大小都不会超过 3n。
方法二：动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int nthUglyNumber3(int n) {
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
dp[i] = Math.min(Math.min(n2, n3), n5);
if (dp[i] == n2) a++;
if (dp[i] == n3) b++;
if (dp[i] == n5) c++;
}
return dp[n - 1];
}
|
复杂度分析
- 时间复杂度 O(N) : 其中 N = n，动态规划需遍历计算 dp 列表。
- 空间复杂度 O(N) : 长度为 N 的 dp 列表使用 O(N) 的额外空间。
题目链接
poj1338