LeetCode 面试题 17.09. 第 k 个数

约 4 分钟
文章信息 3 个分类 4 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
哈希表 动态规划 数学 堆（优先队列）

题目描述

✅ 面试题 17.09. 第 k 个数

image-20260929010451262

题意分析

将所有质因子只能取自 3、5、7 的正整数按从小到大排列，返回第 k 个不同的数。不是必须同时含有这三个因子；1 没有其他质因子，也算第一个数。

解法：三指针有序生成

核心思路

[!blue]

除 1 外，每个合法数都能除去一个 3、5 或 7，得到更小的合法数。因此可以把已有序列分别乘 3、5、7，得到三条递增候选序列，再逐次取它们尚未使用的最小值。

dp[i] 保存第 i + 1 个数，初始 dp[0] = 1。三个指针 p3、p5、p7 分别指向各自候选序列中尚未输出的位置。写入第 i 项前，dp[p3] * 3、dp[p5] * 5、dp[p7] * 7 都是对应序列里严格大于上一答案的最小候选。

为什么取三个候选的最小值不会漏数？设最小的未生成合法数为 v，从它除去任意一个质因子，得到的数更小，必然已经在 dp 中。因此 v 属于某条候选序列；该序列的最早未用项不可能越过 v，三个队首取最小就一定能得到下一个正确值。

将最小值写入 dp 后，所有等于它的候选指针都要前进。每条序列本身严格递增，前进后便超过当前值；没有命中的候选原本就更大，保持不动。这样下一轮继续满足不变量，也消除了不同因子生成同一结果的重复。

解题步骤

  • 创建长度为 k 的 dp，首项置 1，三个指针均置 0。
  • 从 i = 1 开始，计算三个候选乘积，取最小值写入 dp[i]。
  • 分别比较三个候选与当前最小值，命中的指针各自加 1，使用三个独立的 if。
  • 生成满 k 个数后返回 dp[k - 1]。k = 1 时不进入循环，直接返回初始的 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([]int64, 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 int(dp[k-1])
}

复杂度分析

  • 时间复杂度：$O(k)$。每轮生成一个新数，只做固定次数的乘法、比较和指针移动。
  • 空间复杂度：$O(k)$。三个指针可能引用不同的历史位置，需要保留此前生成的序列。

关键点总结

[!green]

  • 生成来源覆盖全部合法数，三条有序序列的队首负责确定下一个最小值。
  • 所有命中当前答案的来源都要推进，才能让下一轮候选严格大于当前值。
  • 1 是生成序列的起点，排名从 1 开始，数组下标从 0 开始。
  • 候选乘积使用 long / int64 计算，返回类型仍沿用题目接口。

易错点总结

[!yellow]

  • 把三个判断写成 if / else if，会只推进一个来源，使当前结果在下一轮重复出现。
  • 没有命中的指针不能一起前进，否则会跳过尚未输出的候选。
  • 不能省略初始值 1，否则所有乘法生成链和第一个排名都会偏移。
  • 当前最小值也必须保存进 dp，后续候选会继续引用这些已经生成的历史项。
  • 乘法前就应使用宽整数保存操作数，不能在窄整数乘法溢出后才转换结果。

相似题目

题目 难度 关联与区别
264. 丑数 II 中等 同样用三指针生成无重复有序序列，原题因子为2、3、5，本题为3、5、7。
313. 超级丑数 中等 把固定三种因子扩展为给定质数集合，需要每种因子的独立候选与去重推进。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/78918787
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！