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没有质因数按惯例被视为丑数。示例 1Input: 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。示例 2Input: 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和98 × 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, n1), 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 }逐行拆解算法原理dp数组dp[i]表示第i个丑数。dp[1] 1是第一个丑数dp[0]仅作占位置0数组长度为n1。三个指针p2, p3, p5分别表示“下一个待与2相乘的丑数在 dp 中的下标”“下一个待与3相乘的丑数下标”“下一个待与5相乘的丑数下标”。初始均为1即都从第一个丑数1开始乘。候选计算第i轮三个候选分别为dp[p2] * 2、dp[p3] * 3、dp[p5] * 5取三者的最小值作为新的丑数dp[i]。因为三路候选各自都是“按已被选出的丑数序列顺序推进”的所以取出的最小值必然大于上一个dp[i-1]序列严格递增。指针推进关键用if而非else if分别判断——哪个候选等于dp[i]对应的指针就前进一位。由于可能存在重复候选如6同时由3 × 2和2 × 3产生三个if独立判断可以保证所有相等路径的指针都同步推进从而在序列中去重。这正是原文档“去重”逻辑在 O(n) 解法中的落地方式。终止与返回循环到i n时dp[n]即为第n个丑数。整个算法每个丑数最多被三个指针各“访问”一次因此时间复杂度为O(n)空间复杂度为O(n)仅一个长度为n1的数组。手动验证以 n 10 为例按上述代码手工推导前几轮可验证序列与题目示例一致ix2x3x5dp[i]推进的指针21×221×331×552p2→232×241×331×553p3→242×242×361×554p2→353×262×361×555p5→263×262×362×5106p2→4 且 p3→3第 6 轮6同时命中 x2 与 x3两个指针同时推进实现了去重。继续推导可得 dp 序列为1, 2, 3, 4, 5, 6, 8, 9, 10, 12dp[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)) } }测试覆盖了文档中的两个官方示例n10 → 12、n1 → 1并额外补充了边界与中间值n6 → 6、n8 → 9、n14 → 20可验证三指针解法在递推过程中的正确性。运行测试的命令以仓库根目录为基准go test -v ./leetcode/ -run Test_Problem264仓库根目录的 gotest.sh 展示了项目整体测试与覆盖率生成方式go test -covermodeatomic -coverprofilecoverage.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 是最优解而大规模参数则需转向二分。小结本题的核心方法论可总结为三点递推生成丑数 × 质因子仍为丑数序列可自底向上构造三指针去排序每个丑数与2/3/5各乘一次用三个指针保证候选有序将 O(n log n) 降为 O(n)独立 if 去重三个指针的推进用独立if判断同步处理相等的候选值天然避免重复。仓库中 题解文档、源码实现 与 测试用例 三件套齐备可直接作为面试复习与算法模板复用。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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没有质因数按惯例被视为丑数。示例 1Input: 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。示例 2Input: 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和98 × 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, n1), 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 }逐行拆解算法原理dp数组dp[i]表示第i个丑数。dp[1] 1是第一个丑数dp[0]仅作占位置0数组长度为n1。三个指针p2, p3, p5分别表示“下一个待与2相乘的丑数在 dp 中的下标”“下一个待与3相乘的丑数下标”“下一个待与5相乘的丑数下标”。初始均为1即都从第一个丑数1开始乘。候选计算第i轮三个候选分别为dp[p2] * 2、dp[p3] * 3、dp[p5] * 5取三者的最小值作为新的丑数dp[i]。因为三路候选各自都是“按已被选出的丑数序列顺序推进”的所以取出的最小值必然大于上一个dp[i-1]序列严格递增。指针推进关键用if而非else if分别判断——哪个候选等于dp[i]对应的指针就前进一位。由于可能存在重复候选如6同时由3 × 2和2 × 3产生三个if独立判断可以保证所有相等路径的指针都同步推进从而在序列中去重。这正是原文档“去重”逻辑在 O(n) 解法中的落地方式。终止与返回循环到i n时dp[n]即为第n个丑数。整个算法每个丑数最多被三个指针各“访问”一次因此时间复杂度为O(n)空间复杂度为O(n)仅一个长度为n1的数组。手动验证以 n 10 为例按上述代码手工推导前几轮可验证序列与题目示例一致ix2x3x5dp[i]推进的指针21×221×331×552p2→232×241×331×553p3→242×242×361×554p2→353×262×361×555p5→263×262×362×5106p2→4 且 p3→3第 6 轮6同时命中 x2 与 x3两个指针同时推进实现了去重。继续推导可得 dp 序列为1, 2, 3, 4, 5, 6, 8, 9, 10, 12dp[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)) } }测试覆盖了文档中的两个官方示例n10 → 12、n1 → 1并额外补充了边界与中间值n6 → 6、n8 → 9、n14 → 20可验证三指针解法在递推过程中的正确性。运行测试的命令以仓库根目录为基准go test -v ./leetcode/ -run Test_Problem264仓库根目录的 gotest.sh 展示了项目整体测试与覆盖率生成方式go test -covermodeatomic -coverprofilecoverage.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 是最优解而大规模参数则需转向二分。小结本题的核心方法论可总结为三点递推生成丑数 × 质因子仍为丑数序列可自底向上构造三指针去排序每个丑数与2/3/5各乘一次用三个指针保证候选有序将 O(n log n) 降为 O(n)独立 if 去重三个指针的推进用独立if判断同步处理相等的候选值天然避免重复。仓库中 题解文档、源码实现 与 测试用例 三件套齐备可直接作为面试复习与算法模板复用。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考