LeetCode 面试题 17.09. 第 k 个数
目录
题目描述
题意分析
定义“魔术数”为质因子只包含 3、5、7 的正整数，1 也算第一个。要求按从小到大、不重复的顺序返回第 k 个。
用最小堆从 1 出发，每弹出一个数就乘 3、5、7，配合集合去重可以做到
O(k log k)。但这些数有更强的生成结构：除 1 外，每个数都能写成某个更早魔术数乘 3、5 或 7，因此可以像合并三条有序链一样线性生成。关键难点是重复，例如 15 既等于
3×5又等于5×3。所有产生当前最小值的指针都必须一起前进。
解法：三指针有序生成
核心思路
dp[i]表示第i+1个魔术数，dp[0]=1。三个指针p3、p5、p7分别指向“尚未乘过对应因子并进入答案”的最早位置。下一项一定是
min(dp[p3]×3, dp[p5]×5, dp[p7]×7)。写入后，哪个候选等于 next，就推进哪个指针；若多个相等则全部推进。不变量是：写入
dp[i]前，三个候选分别是由 3、5、7 生成且严格大于dp[i-1]的最小值。因此取三者最小不会漏数，全部推进又保证下一轮不会重复当前值。以 k=5 为例：从 1 开始，候选
(3,5,7)取 3；接着(9,5,7)取 5；(9,15,7)取 7；(9,15,21)取 9，序列前五项为[1,3,5,7,9]，答案是 9。
解题步骤
- 创建长度 k 的数组，首项置 1，三个指针置 0。
- 从下标 1 开始，计算三种候选的最小值 next。
- 把 next 写入 dp。
- 分别判断三个候选是否等于 next，命中的指针都加一。
- 返回
dp[k-1]。
代码实现
class Solution {
public int getKthMagicNumber(int k) {
long[] dp = new long[k];
dp[0] = 1;
int p3 = 0;
int p5 = 0;
int p7 = 0;
for (int i = 1; i < k; i++) {
long next3 = dp[p3] * 3;
long next5 = dp[p5] * 5;
long next7 = dp[p7] * 7;
long next = Math.min(next3, Math.min(next5, next7));
dp[i] = next;
if (next == next3) {
p3++;
}
if (next == next5) {
p5++;
}
if (next == next7) {
p7++;
}
}
return (int) dp[k - 1];
}
}
func getKthMagicNumber(k int) int {
dp := make([]int, k)
dp[0] = 1
p3, p5, p7 := 0, 0, 0
for i := 1; i < k; i++ {
next3 := dp[p3] * 3
next5 := dp[p5] * 5
next7 := dp[p7] * 7
next := min(next3, min(next5, next7))
dp[i] = next
if next == next3 {
p3++
}
if next == next5 {
p5++
}
if next == next7 {
p7++
}
}
return dp[k-1]
}
复杂度分析
- 时间复杂度：
O(k)，每轮常数次乘法、比较与指针移动。- 空间复杂度：
O(k)，三个指针需要随机读取此前生成的序列。
关键点总结
- 这是三路有序序列合并，不需要堆的
log k代价。- 同一 next 可能来自多个因子，所有相等分支都要用独立
if，不能写成else if。- 1 是第一个数，k 使用一基排名，返回下标
k-1。- 面试追问若因子扩展成任意数组，可推广为每个因子一个指针；因子很多时最小堆更方便，复杂度变为
O(k log m)。
易错点总结
- 只推进一个命中指针：生成 15 时
3×5与5×3同时命中，若只推进 p3，下一轮还会从 p5 生成 15，序列重复。- 把三个判断写成
if/else if：本质上仍只推进一个指针，反例同上。- 忘记把 1 放在首项：k=1 会返回 3，而正确答案是 1。
- 每轮把指针都无条件加一：会跳过候选，例如取 3 后若 p5 也前进，数字 5 将永远丢失。
- 中间乘法使用窄整数且不看约束：较大 k 时可能先溢出成负数并被错误选为最小值；Java 用 long 保存生成序列更稳。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 264. 丑数 II | 中等 | 因子 2、3、5 的三指针同构题 |
| 313. 超级丑数 | 中等 | 因子集合扩展到任意质数数组 |