LeetCode 面试题 17.09 第 k 个数题解堆去重与三指针状态机的双解法剖析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以 leetcode 仓库中 problems/get-kth-magic-number-lcci.md 为核心围绕面试题 17.09「第 k 个数」素因子仅含 3、5、7 的数展开完整继承原文档的题目描述、前置知识与两套 Python 实现并结合仓库内 263. 丑数、1262. 可被三整除的最大和 以及 堆专题 等资料进行源码级纵深扩充。读完本文你将掌握「小顶堆 Set 去重」与「三指针状态机」两种生成丑数类序列的经典套路理解二者在时间复杂度上的本质差异并能举一反三迁移到同类「丑数变体」题目中。题目描述与题意拆解题目原文源自 problems/get-kth-magic-number-lcci.md有些数的素因子只有 357请设计一个算法找出第 k 个数。注意不是必须有这些素因子而是必须不包含其他的素因子。例如前几个数按顺序应该是 135791521。 示例 1: 输入: k 5 输出: 9解题前先精确理解题意的两个关键约束「素因子只有 357」是充分条件而非必要条件即序列中的每个数可以写成 $3^a \times 5^b \times 7^c$$a, b, c$ 为非负整数的形式且不能包含 2、11 等其他任何素因子。例如 9 3² 合法15 3 × 5 合法而 14 2 × 7 因含素因子 2 而不合法。1 是序列的第一项当 $a b c 0$ 时得到 1题目给出的前几个数为1, 3, 5, 7, 9, 15, 21其中 k 5 对应 9。这个问题在数论上被称为「丑数序列」的经典推广判断单个数字是否为丑数可见仓库内 263. 丑数该题限定素因子为 2、3、5通过不断整除 2/3/5 后判断结果是否为 1 完成判定而本题则要求按升序生成这类数的第 k 项属于典型的「生成第 k 小元素」问题。前置知识原文档列出的前置知识为堆、状态机、动态规划。结合仓库内对应专题文章可进一步明确其定位堆优先队列小顶堆可以以 $O(\log n)$ 的成本反复取出当前最小值是「每次取最小、生成下一个」类算法的天然载体基础原理见 堆专题进阶技巧如多路归并视角见 堆进阶状态机多指针推进用三个指针分别记录 3、5、7 三个因子当前对应的最小索引类似归并排序中多路有序流的合并仓库 1262. 可被三整除的最大和 中也有基于状态机思路的解法动态规划三指针方案本质上是维护一个单调递增的候选序列每一轮用三个「候选来源」推导出下一个状态属于递推思想的体现可参考 动态规划专题。解法一小顶堆 Set 去重思路原文档的思路非常直白使用一个小顶堆每次从中取出当前最小值重复取 k 次第 k 次取出的就是答案。具体过程是初始时堆中只有1每次从堆顶弹出最小值cur这个cur必然是当前未输出的最小值将cur * 3、cur * 5、cur * 7三个候选推入堆中——因为序列中任意一个数的下一个合法数必然等于「该数乘以 3 或 5 或 7」重复上述过程 k 次。唯一需要处理的坑重复数字原文档明确指出去重是本解法的关键点。因为生成路径不唯一例如$3 \times 5 15$同时 $5 \times 3 15$$3 \times 7 21$同时 $7 \times 3 21$更一般地$15 \times 7 105$ 与 $35 \times 3 105$ 等也会重复。如果不做去重同一个数会被多次弹出计数导致返回的是「第 k 次出堆的元素」而非「第 k 个不同的数」答案错误。原文档给出的方案是用一个set记录已经入堆过的数。代码Pythonfrom heapq import heappop, heappush class Solution: def getKthMagicNumber(self, k: int) - int: heap [1] numbers set() # 每次从小顶堆取一个 取 k 次即可 while k: cur heappop(heap) if cur not in numbers: k - 1 heappush(heap, cur * 3) heappush(heap, cur * 5) heappush(heap, cur * 7) numbers.add(cur) return cur正确性分析与复杂度推导正确性堆中始终保存着「所有可能成为下一个最小值的候选」。由于乘法只引入更大的数堆顶元素就是全局最小且未输出的数因此第 k 次有效出堆的元素恰为序列升序第 k 项。set保证重复候选如 15 从 3×5 和 5×3 两条路径产生只会被计数一次。复杂度由代码结构推导原文档未显式给出时间复杂度$O(k \log k)$。最多入堆约 $3k$ 个元素每个有效出堆元素产生 3 个候选含重复堆操作单次为 $O(\log k)$空间复杂度$O(k)$。堆与set中同时驻留的元素规模与 k 成正比。优点思路零门槛正确性直观适合作为面试时的第一反应。缺点堆中堆积了大量重复与暂时用不到的候选存在常数较大的冗余当 k 很大如 $10^5$ 以上时$O(k \log k)$ 的代价开始明显。解法二三指针状态机多路归并递推思路这是原文档重点推荐、也是同类题目的最优套路。原文档将它称为「状态机」并引用其此前撰写的《原来状态机也可以用来刷 LeetCode》一文对应仓库内 1262. 可被三整除的最大和 的解法思路说明这类题型的普适性。核心洞察是既然序列中每个数都来自「上一个数 × 3 / × 5 / × 7」那么序列可以看作三路有序流的合并第 1 路将序列每个数乘以 3第 2 路将序列每个数乘以 5第 3 路将序列每个数乘以 7三路分别乘以同一个递增序列因此每路内部都是递增的。每次从三路的「当前头元素」中取最小值作为下一个序列元素就等价于归并三个有序数组——这正是merge k sorted lists的思想仓库 23.merge-k-sorted-lists.md 专门讲解过多路归并。而用三个指针p3, p5, p7替代堆来记录「每路消费到了序列的哪个位置」就把堆的 $O(\log k)$ 单次操作降为 $O(1)$。原文档给出的状态机代码如下代码Pythonclass Solution: def getKthMagicNumber(self, k: int) - int: p3 p5 p7 0 state [1] [0] * (k - 1) for i in range(1, k): state[i] min(state[p3] * 3, state[p5] * 5, state[p7] * 7) if 3 * state[p3] state[i]: p3 1 if 5 * state[p5] state[i]: p5 1 if 7 * state[p7] state[i]: p7 1 return state[-1]逐行拆解与三个容易忽略的细节初始化p3 p5 p7 0三个指针都指向序列第 0 项值为 1state[0] 1取最小state[i] min(state[p3] * 3, state[p5] * 5, state[p7] * 7)从三路候选头中选最小者三个独立的 if 而非 if/elif去重的精髓当多个候选同时等于最小值时例如state[p3] * 3 state[p5] * 5对应的指针全部后移从而天然跳过重复。以序列第 4 项为例state [1, 3, 5, 7] 时state[p3]*3 7*3 21、state[p5]*5 3*5 15、state[p7]*7 1*7 7取 min 7 推入 state[4]——等等这里需要仔细验证一下序列本身。实际上验证k 5 时 state [1, 3, 5, 7, 9]state[4] min(7*3, 3*5, 1*7) min(21, 15, 7) 7这与题目给出的序列1, 3, 5, 7, 9, 15, 21不符。问题在于上述推演中把p3的推进看错了生成第 2 项时state[1] min(1*3, 1*5, 1*7) 3此时3*state[p3] 3成立p3变为 1生成第 3 项时state[2] min(state[1]*39, 1*55, 1*77) 5p5变为 1生成第 4 项时state[3] min(9, 5*5? no...)——推演要严格按指针所指的 state 下标进行此时 p31、p51、p70state[3] min(state[1]*39, state[1]*515, state[0]*77) 7p7变为 1。生成第 5 项时 p31、p51、p71state[4] min(9, 15, 21) 9p3变为 2。于是得到前五项 1, 3, 5, 7, 9与题目完全一致。状态数组的下标即「第几个数」最终state[-1]就是第 k 个数。复杂度分析原文档明确给出时间复杂度$O(k)$每轮仅做常数次乘法和比较三指针各自单调递增、总共只移动 $O(k)$ 次空间复杂度$O(k)$用于存储状态数组。相比堆解法三指针方案把每次选最小值从 $O(\log k)$ 摊薄到 $O(1)$且没有重复元素的冗余生成是本题在时间维度上的最优解。双解法对比与选型建议维度小顶堆 Set三指针状态机核心数据结构堆优先队列 哈希集合三个指针 状态数组去重方式显式 set 判断多个 if 同时推进指针天然去重时间复杂度$O(k \log k)$$O(k)$空间复杂度$O(k)$$O(k)$思路直观度高直接模拟取最小中需要理解多路归并适用场景对 k 不大、快速出解法友好k 较大或追求最优解面试建议先讲堆解法证明思路建模 去重两个关键点再过渡到三指针状态机说明优化动机展示从「通用工具」到「问题特化」的思考路径。从仓库源码看同类题型的知识延伸本题并非孤立存在仓库中多个文件与之构成「丑数」知识族263. 丑数本题的判定版素因子为 2、3、5通过反复整除判断是否为丑数。两者的关系是263 考察「判单点」本题考察「按序生成」。若把 263 的因子换成 3、5、7 并改为生成型即为本题1262. 可被三整除的最大和原文档状态机一节的引用出处同样用「按余数分组 状态推进」的思路解题可作为状态机套路在其他题目上的印证堆进阶将「每次取最小、生成新候选」抽象为多路归并问题的理论背景与本题堆解法的建模一脉相承。此外原文档将其归入「堆」考点该题已收录于仓库的 collections/medium.md中等难度题单与 SUMMARY.md目录中的「数学」相关章节读者可在仓库目录结构中快速定位同类题目进行刷题串联。总结面试题 17.09「第 k 个数」是「丑数类」生成问题的代表堆解法以「小顶堆每次取最小 Set 去重」直球建模胜在直观代价是 $O(k \log k)$ 时间与重复候选的冗余三指针状态机把问题还原为三路有序流归并用三个指针 O(1) 选最小、多 if 同时推进去重将时间优化到线性 $O(k)$是本题的标准最优解。两种解法的完整 Python 实现与复杂度分析均已在上文给出可直接在本地 LeetCode 环境验证如 k 5 应返回 9。掌握「去重生成序列」与「多路指针递推」这两个核心套路后可以继续挑战仓库内 264 类丑数系列变体 及更多堆与状态机相关的进阶题目。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/19 21:17:19 · 阅读 1.2k LeetCode 面试题 17.09 第 k 个数题解：堆去重与三指针状态机的双解法剖析
LeetCode 面试题 17.09 第 k 个数题解堆去重与三指针状态机的双解法剖析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以 leetcode 仓库中 problems/get-kth-magic-number-lcci.md 为核心围绕面试题 17.09「第 k 个数」素因子仅含 3、5、7 的数展开完整继承原文档的题目描述、前置知识与两套 Python 实现并结合仓库内 263. 丑数、1262. 可被三整除的最大和 以及 堆专题 等资料进行源码级纵深扩充。读完本文你将掌握「小顶堆 Set 去重」与「三指针状态机」两种生成丑数类序列的经典套路理解二者在时间复杂度上的本质差异并能举一反三迁移到同类「丑数变体」题目中。题目描述与题意拆解题目原文源自 problems/get-kth-magic-number-lcci.md有些数的素因子只有 357请设计一个算法找出第 k 个数。注意不是必须有这些素因子而是必须不包含其他的素因子。例如前几个数按顺序应该是 135791521。 示例 1: 输入: k 5 输出: 9解题前先精确理解题意的两个关键约束「素因子只有 357」是充分条件而非必要条件即序列中的每个数可以写成 $3^a \times 5^b \times 7^c$$a, b, c$ 为非负整数的形式且不能包含 2、11 等其他任何素因子。例如 9 3² 合法15 3 × 5 合法而 14 2 × 7 因含素因子 2 而不合法。1 是序列的第一项当 $a b c 0$ 时得到 1题目给出的前几个数为1, 3, 5, 7, 9, 15, 21其中 k 5 对应 9。这个问题在数论上被称为「丑数序列」的经典推广判断单个数字是否为丑数可见仓库内 263. 丑数该题限定素因子为 2、3、5通过不断整除 2/3/5 后判断结果是否为 1 完成判定而本题则要求按升序生成这类数的第 k 项属于典型的「生成第 k 小元素」问题。前置知识原文档列出的前置知识为堆、状态机、动态规划。结合仓库内对应专题文章可进一步明确其定位堆优先队列小顶堆可以以 $O(\log n)$ 的成本反复取出当前最小值是「每次取最小、生成下一个」类算法的天然载体基础原理见 堆专题进阶技巧如多路归并视角见 堆进阶状态机多指针推进用三个指针分别记录 3、5、7 三个因子当前对应的最小索引类似归并排序中多路有序流的合并仓库 1262. 可被三整除的最大和 中也有基于状态机思路的解法动态规划三指针方案本质上是维护一个单调递增的候选序列每一轮用三个「候选来源」推导出下一个状态属于递推思想的体现可参考 动态规划专题。解法一小顶堆 Set 去重思路原文档的思路非常直白使用一个小顶堆每次从中取出当前最小值重复取 k 次第 k 次取出的就是答案。具体过程是初始时堆中只有1每次从堆顶弹出最小值cur这个cur必然是当前未输出的最小值将cur * 3、cur * 5、cur * 7三个候选推入堆中——因为序列中任意一个数的下一个合法数必然等于「该数乘以 3 或 5 或 7」重复上述过程 k 次。唯一需要处理的坑重复数字原文档明确指出去重是本解法的关键点。因为生成路径不唯一例如$3 \times 5 15$同时 $5 \times 3 15$$3 \times 7 21$同时 $7 \times 3 21$更一般地$15 \times 7 105$ 与 $35 \times 3 105$ 等也会重复。如果不做去重同一个数会被多次弹出计数导致返回的是「第 k 次出堆的元素」而非「第 k 个不同的数」答案错误。原文档给出的方案是用一个set记录已经入堆过的数。代码Pythonfrom heapq import heappop, heappush class Solution: def getKthMagicNumber(self, k: int) - int: heap [1] numbers set() # 每次从小顶堆取一个 取 k 次即可 while k: cur heappop(heap) if cur not in numbers: k - 1 heappush(heap, cur * 3) heappush(heap, cur * 5) heappush(heap, cur * 7) numbers.add(cur) return cur正确性分析与复杂度推导正确性堆中始终保存着「所有可能成为下一个最小值的候选」。由于乘法只引入更大的数堆顶元素就是全局最小且未输出的数因此第 k 次有效出堆的元素恰为序列升序第 k 项。set保证重复候选如 15 从 3×5 和 5×3 两条路径产生只会被计数一次。复杂度由代码结构推导原文档未显式给出时间复杂度$O(k \log k)$。最多入堆约 $3k$ 个元素每个有效出堆元素产生 3 个候选含重复堆操作单次为 $O(\log k)$空间复杂度$O(k)$。堆与set中同时驻留的元素规模与 k 成正比。优点思路零门槛正确性直观适合作为面试时的第一反应。缺点堆中堆积了大量重复与暂时用不到的候选存在常数较大的冗余当 k 很大如 $10^5$ 以上时$O(k \log k)$ 的代价开始明显。解法二三指针状态机多路归并递推思路这是原文档重点推荐、也是同类题目的最优套路。原文档将它称为「状态机」并引用其此前撰写的《原来状态机也可以用来刷 LeetCode》一文对应仓库内 1262. 可被三整除的最大和 的解法思路说明这类题型的普适性。核心洞察是既然序列中每个数都来自「上一个数 × 3 / × 5 / × 7」那么序列可以看作三路有序流的合并第 1 路将序列每个数乘以 3第 2 路将序列每个数乘以 5第 3 路将序列每个数乘以 7三路分别乘以同一个递增序列因此每路内部都是递增的。每次从三路的「当前头元素」中取最小值作为下一个序列元素就等价于归并三个有序数组——这正是merge k sorted lists的思想仓库 23.merge-k-sorted-lists.md 专门讲解过多路归并。而用三个指针p3, p5, p7替代堆来记录「每路消费到了序列的哪个位置」就把堆的 $O(\log k)$ 单次操作降为 $O(1)$。原文档给出的状态机代码如下代码Pythonclass Solution: def getKthMagicNumber(self, k: int) - int: p3 p5 p7 0 state [1] [0] * (k - 1) for i in range(1, k): state[i] min(state[p3] * 3, state[p5] * 5, state[p7] * 7) if 3 * state[p3] state[i]: p3 1 if 5 * state[p5] state[i]: p5 1 if 7 * state[p7] state[i]: p7 1 return state[-1]逐行拆解与三个容易忽略的细节初始化p3 p5 p7 0三个指针都指向序列第 0 项值为 1state[0] 1取最小state[i] min(state[p3] * 3, state[p5] * 5, state[p7] * 7)从三路候选头中选最小者三个独立的 if 而非 if/elif去重的精髓当多个候选同时等于最小值时例如state[p3] * 3 state[p5] * 5对应的指针全部后移从而天然跳过重复。以序列第 4 项为例state [1, 3, 5, 7] 时state[p3]*3 7*3 21、state[p5]*5 3*5 15、state[p7]*7 1*7 7取 min 7 推入 state[4]——等等这里需要仔细验证一下序列本身。实际上验证k 5 时 state [1, 3, 5, 7, 9]state[4] min(7*3, 3*5, 1*7) min(21, 15, 7) 7这与题目给出的序列1, 3, 5, 7, 9, 15, 21不符。问题在于上述推演中把p3的推进看错了生成第 2 项时state[1] min(1*3, 1*5, 1*7) 3此时3*state[p3] 3成立p3变为 1生成第 3 项时state[2] min(state[1]*39, 1*55, 1*77) 5p5变为 1生成第 4 项时state[3] min(9, 5*5? no...)——推演要严格按指针所指的 state 下标进行此时 p31、p51、p70state[3] min(state[1]*39, state[1]*515, state[0]*77) 7p7变为 1。生成第 5 项时 p31、p51、p71state[4] min(9, 15, 21) 9p3变为 2。于是得到前五项 1, 3, 5, 7, 9与题目完全一致。状态数组的下标即「第几个数」最终state[-1]就是第 k 个数。复杂度分析原文档明确给出时间复杂度$O(k)$每轮仅做常数次乘法和比较三指针各自单调递增、总共只移动 $O(k)$ 次空间复杂度$O(k)$用于存储状态数组。相比堆解法三指针方案把每次选最小值从 $O(\log k)$ 摊薄到 $O(1)$且没有重复元素的冗余生成是本题在时间维度上的最优解。双解法对比与选型建议维度小顶堆 Set三指针状态机核心数据结构堆优先队列 哈希集合三个指针 状态数组去重方式显式 set 判断多个 if 同时推进指针天然去重时间复杂度$O(k \log k)$$O(k)$空间复杂度$O(k)$$O(k)$思路直观度高直接模拟取最小中需要理解多路归并适用场景对 k 不大、快速出解法友好k 较大或追求最优解面试建议先讲堆解法证明思路建模 去重两个关键点再过渡到三指针状态机说明优化动机展示从「通用工具」到「问题特化」的思考路径。从仓库源码看同类题型的知识延伸本题并非孤立存在仓库中多个文件与之构成「丑数」知识族263. 丑数本题的判定版素因子为 2、3、5通过反复整除判断是否为丑数。两者的关系是263 考察「判单点」本题考察「按序生成」。若把 263 的因子换成 3、5、7 并改为生成型即为本题1262. 可被三整除的最大和原文档状态机一节的引用出处同样用「按余数分组 状态推进」的思路解题可作为状态机套路在其他题目上的印证堆进阶将「每次取最小、生成新候选」抽象为多路归并问题的理论背景与本题堆解法的建模一脉相承。此外原文档将其归入「堆」考点该题已收录于仓库的 collections/medium.md中等难度题单与 SUMMARY.md目录中的「数学」相关章节读者可在仓库目录结构中快速定位同类题目进行刷题串联。总结面试题 17.09「第 k 个数」是「丑数类」生成问题的代表堆解法以「小顶堆每次取最小 Set 去重」直球建模胜在直观代价是 $O(k \log k)$ 时间与重复候选的冗余三指针状态机把问题还原为三路有序流归并用三个指针 O(1) 选最小、多 if 同时推进去重将时间优化到线性 $O(k)$是本题的标准最优解。两种解法的完整 Python 实现与复杂度分析均已在上文给出可直接在本地 LeetCode 环境验证如 k 5 应返回 9。掌握「去重生成序列」与「多路指针递推」这两个核心套路后可以继续挑战仓库内 264 类丑数系列变体 及更多堆与状态机相关的进阶题目。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考