LeetCode 264. 丑数 II
目录
题目描述
题意分析
丑数的定义是「质因数分解后只含 2、3、5 这三个质因子」的正整数，并且规定 1 也是丑数（它的质因数分解为空，不含任何其他质因子）。题目要求返回从小到大数的第
n个丑数。要注意「第
n个」这个说法暗含了一个前提：丑数必须按严格递增的顺序去数，相同的数只算一次。所以任何生成方案都必须同时保证两件事——不遗漏，也不重复。遗漏会让序号偏小、答案偏大，重复会让序号偏大、答案偏小，两类错误都会直接导致结果不对。约束信号方面，
n的上界通常是 1690，对应的第 1690 个丑数是 2123366400，恰好落在 32 位有符号整数范围内，这个上界不是随手定的，正是为了保证int不溢出。同时n至少为 1，不需要处理n为 0 的情况。数据规模这么小，说明出题人期待的是一个 $O(n)$ 或 $O(n \log n)$ 的构造性做法，而不是在整个整数域上做判定。边界情形有：
n = 1时答案是 1，此时循环一次都不执行，全靠初始化给出答案；n较小时前几个丑数是 1、2、3、4、5、6，注意 7 不是丑数而 8 是，序列并不连续。
解法：三指针动态生成
核心思路
从 1 开始逐个整数判断是否为丑数，耗时取决于第
n个丑数的数值；当n = 1690时要检查到 21 亿附近。更合适的做法是只生成丑数。除了 1，每个丑数都能由某个更小的丑数乘 2、3 或 5 得到。因此，若
\[2 \times dp[0],2 \times dp[1],\ldots\] \[3 \times dp[0],3 \times dp[1],\ldots\] \[5 \times dp[0],5 \times dp[1],\ldots\]dp已按升序保存生成结果，后续候选来自三条有序序列：用
p2、p3、p5分别指向三条序列中尚未输出的最小候选。每轮取三个候选的最小值写入dp，就相当于合并三条有序序列。循环不变量是：
dp[0..i-1]为前i个严格递增的丑数；dp[p2]×2、dp[p3]×3、dp[p5]×5分别是对应生成链中第一个未消费的值。取最小值保证顺序且不会遗漏。若同一个数由多条链产生，例如6 = 2×3 = 3×2，所有命中的指针都必须前移，才能只输出一次。初始
dp[0] = 1。上述结构性质保证每个更大的丑数必在三条生成链中；三路归并又始终取全局最小未消费值，因此结果无遗漏、严格递增，第n个生成值就是答案。
解题步骤
- 创建长度为
n的数组，令dp[0] = 1。- 初始化
p2 = p3 = p5 = 0。- 从
i = 1开始，计算dp[p2]×2、dp[p3]×3、dp[p5]×5。- 取三者最小值写入
dp[i]。- 对每个等于最小值的候选，分别推进对应指针；这里必须使用三个独立的
if。- 返回
dp[n-1]。前几个候选依次生成
1,2,3,4,5。下一轮，2 倍链与 3 倍链都产生 6，写入一次后p2、p3同时前移；随后得到8,9,10,12。所以n = 10时答案为 12。
代码实现
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int p2 = 0;
int p3 = 0;
int p5 = 0;
for (int i = 1; i < n; i++) {
int next2 = dp[p2] * 2;
int next3 = dp[p3] * 3;
int next5 = dp[p5] * 5;
int next = Math.min(next2, Math.min(next3, next5));
dp[i] = next;
if (next == next2) {
p2++;
}
if (next == next3) {
p3++;
}
if (next == next5) {
p5++;
}
}
return dp[n - 1];
}
}
func nthUglyNumber(n int) int {
dp := make([]int, n)
dp[0] = 1
p2, p3, p5 := 0, 0, 0
for i := 1; i < n; i++ {
next2 := dp[p2] * 2
next3 := dp[p3] * 3
next5 := dp[p5] * 5
next := min(next2, min(next3, next5))
dp[i] = next
if next == next2 {
p2++
}
if next == next3 {
p3++
}
if next == next5 {
p5++
}
}
return dp[n-1]
}
复杂度分析
- 时间复杂度：
O(n)。共生成n - 1个新丑数，每轮只做常数次比较和指针移动。- 空间复杂度：
O(n)。三个指针需要访问此前生成的丑数，因此保存长度为n的序列。
关键点总结
- 丑数集合稀疏，应从已有丑数构造后继，而不是逐个检查普通整数。
- 本题本质是合并三条有序生成链，三个指针各自记录消费进度。
- 候选相等时必须推进所有来源，才能保证结果严格递增。
dp[0] = 1是生成序列的起点；第n个数对应下标n - 1。- 本题约束保证结果和计算中的候选可用
int；若扩大n，乘法需改为 64 位并检查溢出。
易错点总结
- 用
if / else if推进指针：生成 6 时只移动一个来源，下一轮会再次写入 6，后续序号全部错位。- 忘记把 1 作为第一个丑数：
n = 1应直接返回 1，循环也应从下标 1 开始。- 返回
dp[n]：数组下标从 0 开始，第n个值位于dp[n-1]。- 先移动指针再写最小值：指针已指向下一候选，会跳过刚刚选出的丑数。
- 三条生成链共用一个指针：它们的消费速度不同，例如生成 6 后三个位置并不相同，共用会漏掉 8 或 9。
- 堆解法不去重：6 会由 2×3 和 3×2 两次入堆并被计数两次；三指针方案通过同时推进天然去重。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 263. 丑数 | 简单 | 只判定单个数是否为丑数，反复除以 2、3、5 即可，不涉及按序生成 |
| 剑指 Offer 49. 丑数 | 中等 | 与本题完全同题，可用同一份三指针代码直接通过 |
| 313. 超级丑数 | 中等 | 质因子由固定的三个变成给定数组，三个指针要推广成长度为 k 的指针数组 |
| 1201. 丑数 III | 中等 | 定义改为「能被 a、b、c 之一整除」，规模巨大，须改用二分加容斥而非逐个生成 |
| 面试题 17.09. 第 k 个数 | 中等 | 质因子换成 3、5、7，用来检验三指针模板是否真正理解而非死记 2、3、5 |