Appearance
实战：丑数 II
找出第 n 个丑数。丑数是只包含质因子 2、3、5 的正整数。
问题描述
LeetCode 264. Ugly Number II
丑数是只包含质因子 2、3 或 5 的正整数。给你一个整数 n，返回第 n 个丑数。1 被视为第一个丑数。
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是前 10 个丑数示例 2：
输入：n = 1
输出：1约束条件：
1 <= n <= 1690
问题分析
丑数的性质
丑数只有质因子 2、3、5，这意味着：
- 1 是丑数（特殊情况）
- 任何丑数 × 2、× 3、× 5 还是丑数
- 所有丑数都可以表示为 2^a × 3^b × 5^c（a, b, c ≥ 0）
丑数序列：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ...
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
2^0 2^1 3 2^2 5 2×3 2^3 3^2 2×5 2^2×3 3×5 2^4核心思路
每个丑数都是由更小的丑数乘以 2、3 或 5 得到的。问题是如何按顺序生成丑数？
解法一：最小堆
用最小堆来保证每次取出的都是最小的丑数：
- 从 1 开始
- 每次取出最小的丑数 x
- 把 x×2、x×3、x×5 加入堆
- 用 Set 去重（因为同一个丑数可能被多次生成）
javascript
function nthUglyNumber(n) {
const heap = new MinHeap();
const seen = new Set();
heap.insert(1);
seen.add(1);
let ugly = 1;
for (let i = 0; i < n; i++) {
ugly = heap.extract();
// 生成新的丑数
for (const factor of [2, 3, 5]) {
const next = ugly * factor;
if (!seen.has(next)) {
seen.add(next);
heap.insert(next);
}
}
}
return ugly;
}执行过程：
n = 5
i=0: 取出 1, 加入 2,3,5
堆: [2,3,5], ugly=1
i=1: 取出 2, 加入 4,6,10
堆: [3,4,5,6,10], ugly=2
i=2: 取出 3, 加入 6(重复),9,15
堆: [4,5,6,9,10,15], ugly=3
i=3: 取出 4, 加入 8,12,20
堆: [5,6,8,9,10,12,15,20], ugly=4
i=4: 取出 5, ugly=5
返回 5复杂度分析：
- 时间：O(n log n)，每次操作堆 O(log n)
- 空间：O(n)，堆和 Set 各存储约 3n 个元素
解法二：三指针（动态规划）
更高效的方法是用三个指针，分别表示下一个要乘 2、3、5 的丑数位置：
核心思想：
- 维护一个丑数数组 dp
- 用 p2、p3、p5 分别指向"乘以 2/3/5 后可能是下一个丑数"的位置
- 每次取三个候选值的最小值
javascript
function nthUglyNumber(n) {
const dp = [1];
let p2 = 0, p3 = 0, p5 = 0;
for (let i = 1; i < n; i++) {
// 三个候选值
const next2 = dp[p2] * 2;
const next3 = dp[p3] * 3;
const next5 = dp[p5] * 5;
// 取最小值作为下一个丑数
const next = Math.min(next2, next3, next5);
dp.push(next);
// 更新指针（注意：可能有多个指针同时产生相同的值）
if (next === next2) p2++;
if (next === next3) p3++;
if (next === next5) p5++;
}
return dp[n - 1];
}三指针执行过程详解
初始：dp = [1], p2=0, p3=0, p5=0
i=1:
next2 = dp[0]*2 = 2
next3 = dp[0]*3 = 3
next5 = dp[0]*5 = 5
min = 2, dp = [1, 2], p2=1
i=2:
next2 = dp[1]*2 = 4
next3 = dp[0]*3 = 3
next5 = dp[0]*5 = 5
min = 3, dp = [1, 2, 3], p3=1
i=3:
next2 = dp[1]*2 = 4
next3 = dp[1]*3 = 6
next5 = dp[0]*5 = 5
min = 4, dp = [1, 2, 3, 4], p2=2
i=4:
next2 = dp[2]*2 = 6
next3 = dp[1]*3 = 6
next5 = dp[0]*5 = 5
min = 5, dp = [1, 2, 3, 4, 5], p5=1
i=5:
next2 = dp[2]*2 = 6
next3 = dp[1]*3 = 6
next5 = dp[1]*5 = 10
min = 6, dp = [1, 2, 3, 4, 5, 6], p2=3, p3=2 ← 注意：6 由两种方式生成
...关键点：当 next2 == next3 时，两个指针都要移动，避免重复添加同一个丑数。
复杂度分析：
- 时间：O(n)
- 空间：O(n)
为什么三指针有效？
问题：为什么只需要三个指针就能保证不遗漏任何丑数？
回答：
- 每个丑数都是由更小的丑数乘以 2、3 或 5 得到
- 三个指针确保了每个丑数都会被乘以 2、3、5
- 指针只前进不后退，保证每个丑数只被考虑一次
可视化：
dp: 1 2 3 4 5 6 8 9 10 12
↑ ↑ ↑
p5 p3 p2
下一轮候选：
dp[p2] × 2 = 4 × 2 = 8
dp[p3] × 3 = 2 × 3 = 6 ← 最小
dp[p5] × 5 = 1 × 5 = 5两种方法对比
| 方法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| 最小堆 | O(n log n) | O(n) | 直观易懂，但有去重开销 |
| 三指针 | O(n) | O(n) | 更高效，无重复计算 |
边界情况
javascript
// 测试用例
nthUglyNumber(1); // → 1（第一个丑数）
nthUglyNumber(2); // → 2
nthUglyNumber(10); // → 12
nthUglyNumber(1690);// → 2123366400（最大测试用例）常见错误
1. 三指针不同时更新
javascript
// ❌ 错误：用 else if
if (next === next2) {
p2++;
} else if (next === next3) {
p3++;
} else {
p5++;
}
// 当 next2 == next3 时，只更新了 p2，遗漏了 p3
// ✅ 正确：用独立的 if
if (next === next2) p2++;
if (next === next3) p3++;
if (next === next5) p5++;2. 堆方法忘记去重
javascript
// ❌ 错误：不去重
for (const factor of [2, 3, 5]) {
heap.insert(ugly * factor); // 可能重复添加
}
// ✅ 正确：用 Set 去重
if (!seen.has(next)) {
seen.add(next);
heap.insert(next);
}3. 数值溢出
javascript
// 在某些语言中需要注意
// JavaScript 的 Number 足够大，不会溢出
// 但如果用其他语言，需要用 long 类型相关题目
| 题目 | 难度 | 关联点 |
|---|---|---|
| 263. 丑数 | 简单 | 判断是否为丑数 |
| 313. 超级丑数 | 中等 | 质因子由数组给定 |
| 1201. 丑数 III | 中等 | 二分 + 容斥原理 |
小结
本题展示了两种生成有序序列的方法：
- 最小堆：通用方法，适合任意生成规则
- 多指针：利用序列的特殊结构，更高效
关键技巧：
- 理解丑数的递推性质：新丑数 = 旧丑数 × 质因子
- 三指针确保不遗漏、不重复
- 同一个值可能由多个指针生成，需要同时更新
这种多指针技巧还可以用于合并多个有序数组、生成其他有规律的序列等问题。