LeetCode-Go 题解精讲：264. Ugly Number II 三指针动态规划求第 n 个丑数

LeetCode-Go 题解精讲：264. Ugly Number II 三指针动态规划求第 n 个丑数

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本篇以 LeetCode-Go 仓库中 264. Ugly Number II 的题解文档为骨架，完整讲解“丑数”这一经典数论序列问题的两种解法：最小堆 + map 去重的朴素思路，以及仓库实际采用的三指针动态规划 O(n) 线性解法。读完本文，你将掌握丑数序列的生成规律、三指针消去排序开销的底层原理，并能直接复用仓库中的可运行代码与测试用例验证结果。

题目回顾：什么是丑数

Given an integern, returnthenthugly number.Ugly numberis a positive number whose prime factors only include2,3, and/or5.

丑数（Ugly Number）是一个正整数，其质因数只包含2、3和/或5。注意这里是“只包含”而非“必须包含”，因此1没有质因数，按惯例被视为丑数。

示例 1：

Input: n = 10 Output: 12 Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

前 10 个丑数依次为1, 2, 3, 4, 5, 6, 8, 9, 10, 12，第 10 个丑数为12。注意序列中不会出现7、11等含有其他质因数的数，也不会出现14 = 2 × 7。

示例 2：

Input: n = 1 Output: 1 Explanation: 1 is typically treated as an ugly number.

约束条件：

• 1 <= n <= 1690

仓库题解文档中对应的中文表述为：“给你一个整数n，请你找出并返回第n个丑数。丑数就是只包含质因数2、3和/或5的正整数。”（见 README.md）

解题思路一：最小堆 + map 去重（O(n log n)）

核心思想：从丑数生成丑数

一个最直观的观察是：任意丑数乘以2、3或5之后，得到的仍然是丑数。因为一个只含质因数2/3/5的数，乘上2/3/5后质因数集合不会新增其他质数。

因此可以从最小的丑数1出发，用它与2、3、5相乘得到2, 3, 5；再对这批新数分别与2、3、5相乘，得到更多的丑数候选。把所有候选去重后从小到大排列，第n个数即为答案。

为什么需要堆和 map

原文档明确指出这种朴素生成法的两个关键配套：

• 排序用最小堆实现：每次从堆顶弹出当前最小的候选丑数，保证取数顺序从小到大；
• 去重用 map 实现：同一个丑数可能由不同的乘法路径生成（例如6 = 3 × 2 = 2 × 3），需要用哈希表记录已生成的数，避免重复入堆。

每轮弹出最小值、再压入新的候选，堆操作的时间复杂度为 O(log n)，总共处理 O(n) 个丑数，因此整体时间复杂度为O(n log n)，空间复杂度O(n)（堆与 map 各存 O(n) 个元素）。

仓库的 structures/Heap.go 中就提供了实现container/heap接口的最小堆intHeap，其Less方法以h[i] < h[j]定义最小堆序，可用于这类场景：

package structures // intHeap 实现了最小堆 heap 的接口 type intHeap []int func (h intHeap) Len() int { return len(h) } func (h intHeap) Less(i, j int) bool { return h[i] < h[j] } func (h intHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *intHeap) Push(x interface{}) { *h = append(*h, x.(int)) } func (h *intHeap) Pop() interface{} { res := (*h)[len(*h)-1] *h = (*h)[:len(*h)-1] return res }

此外，structures/PriorityQueue.go 还提供了一个更通用的优先级队列封装（PQ类型，元素为带优先级的entry），当需要携带“该丑数由哪个质因子乘来”等附加信息时可以作为扩展参考。

朴素解法的瓶颈

原文档点出了关键缺陷：“上面的解法耗时在排序中”。产生排序需求的根源在于：小的丑数乘以5可能大于大的丑数乘以2。例如当前集合中已有8和9，8 × 2 = 16而9 × 2 = 18，但8 × 5 = 40明显大于18。候选的生成顺序天然是乱序的，必须借助堆来维护全局有序，代价就是每次入堆出堆的 O(log n) 排序开销。

解题思路二：三指针动态规划（O(n)）

去掉排序的关键观察

原文档用一个递推示例说明了如何避免排序：初始状态丑数只有{1}，乘以2, 3, 5后，将最小的结果存入集合，得到{1, 2}。下一轮相乘时，上一轮1已经和2相乘过，这一轮1不再和2相乘，只与3, 5相乘；而2则与2, 3, 5相乘。将最小的结果存入集合，得到{1, 2, 3}。按此策略继续，每轮选出的丑数天然有序且不重复。

这样做的本质是：每个已有的丑数只需要和三个质因子各乘一次。用一个“指针”记录每个质因子2/3/5已经乘到序列中的哪个位置，下一轮就从该位置之后继续，从而保证每一轮取出的最小值恰好构成严格递增的丑数序列，彻底消除排序。

原文档的结论是：“具体实现利用 3 个指针和一个数组即可实现。时间复杂度 O(n)，空间复杂度 O(n)。”

仓库源码：三指针 DP 实现

仓库中的实际实现位于 leetcode/0264.Ugly-Number-II/264. Ugly Number II.go，与题解文档中的代码完全一致：

package leetcode func nthUglyNumber(n int) int { dp, p2, p3, p5 := make([]int, n+1), 1, 1, 1 dp[0], dp[1] = 0, 1 for i := 2; i <= n; i++ { x2, x3, x5 := dp[p2]*2, dp[p3]*3, dp[p5]*5 dp[i] = min(min(x2, x3), x5) if dp[i] == x2 { p2++ } if dp[i] == x3 { p3++ } if dp[i] == x5 { p5++ } } return dp[n] } func min(a, b int) int { if a < b { return a } return b }

逐行拆解算法原理

1. dp数组：dp[i]表示第i个丑数。dp[1] = 1是第一个丑数，dp[0]仅作占位（置0），数组长度为n+1。

2. 三个指针p2, p3, p5：分别表示“下一个待与2相乘的丑数在 dp 中的下标”“下一个待与3相乘的丑数下标”“下一个待与5相乘的丑数下标”。初始均为1，即都从第一个丑数1开始乘。

3. 候选计算：第i轮，三个候选分别为dp[p2] * 2、dp[p3] * 3、dp[p5] * 5，取三者的最小值作为新的丑数dp[i]。因为三路候选各自都是“按已被选出的丑数序列顺序推进”的，所以取出的最小值必然大于上一个dp[i-1]，序列严格递增。

4. 指针推进（关键）：用if而非else if分别判断——哪个候选等于dp[i]，对应的指针就前进一位。由于可能存在重复候选（如6同时由3 × 2和2 × 3产生），三个if独立判断可以保证所有相等路径的指针都同步推进，从而在序列中去重。这正是原文档“去重”逻辑在 O(n) 解法中的落地方式。

5. 终止与返回：循环到i = n时，dp[n]即为第n个丑数。

整个算法每个丑数最多被三个指针各“访问”一次，因此时间复杂度为O(n)，空间复杂度为O(n)（仅一个长度为n+1的数组）。

手动验证：以 n = 10 为例

按上述代码手工推导前几轮，可验证序列与题目示例一致：

第 6 轮6同时命中 x2 与 x3，两个指针同时推进，实现了去重。继续推导可得 dp 序列为1, 2, 3, 4, 5, 6, 8, 9, 10, 12，dp[10] = 12，与题目输出完全吻合。

测试用例与运行验证

仓库为本题配备了完整的单元测试，位于 leetcode/0264.Ugly-Number-II/264. Ugly Number II_test.go，采用本仓库统一的para/ans表驱动结构：

func Test_Problem264(t *testing.T) { qs := []question264{ {para264{10}, ans264{12}}, {para264{1}, ans264{1}}, {para264{6}, ans264{6}}, {para264{8}, ans264{9}}, {para264{14}, ans264{20}}, } ... for _, q := range qs { _, p := q.ans264, q.para264 fmt.Printf("【input】:%v 【output】:%v\n", p, nthUglyNumber(p.one)) } }

测试覆盖了文档中的两个官方示例（n=10 → 12、n=1 → 1），并额外补充了边界与中间值（n=6 → 6、n=8 → 9、n=14 → 20），可验证三指针解法在递推过程中的正确性。

运行测试的命令（以仓库根目录为基准）：

go test -v ./leetcode/ -run Test_Problem264

仓库根目录的 gotest.sh 展示了项目整体测试与覆盖率生成方式（go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...），本题的测试同样纳入该体系，保证 100% 的测试覆盖目标。

扩展：丑数问题的变体（1201. Ugly Number III）

理解本题后，可顺带对比仓库中的变体题 1201. Ugly Number III：它把固定的质因子2,3,5推广为任意给定的三个数a, b, c，且n可高达10^9，此时 O(n) 的 DP 不可行，仓库采用二分答案 + 容斥原理计数解决：

func nthUglyNumber(n int, a int, b int, c int) int { low, high := int64(0), int64(2*1e9) for low < high { mid := low + (high-low)>>1 if calNthCount(mid, int64(a), int64(b), int64(c)) < int64(n) { low = mid + 1 } else { high = mid } } return int(low) }

其中calNthCount用容斥原理计算[1, num]内能被a/b/c整除的数的个数（含三者最小公倍数项的去重修正）。这一对比恰好体现了同一“丑数”主题在不同数据规模下的两种策略取舍：本题n ≤ 1690，线性 DP 是最优解；而大规模参数则需转向二分。

小结

本题的核心方法论可总结为三点：

1. 递推生成：丑数 × 质因子仍为丑数，序列可自底向上构造；
2. 三指针去排序：每个丑数与2/3/5各乘一次，用三个指针保证候选有序，将 O(n log n) 降为 O(n)；
3. 独立 if 去重：三个指针的推进用独立if判断，同步处理相等的候选值，天然避免重复。

仓库中 题解文档、源码实现 与 测试用例 三件套齐备，可直接作为面试复习与算法模板复用。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go