LeetCode 668. 乘法表中第k小的数

2021-04-23 HGNULB 约 13 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 668. 乘法表中第k小的数

题意分析

想象一张 $m$ 行 $n$ 列的乘法表，第 $i$ 行第 $j$ 列的值是 $i \times j$（下标从 1 开始）。把表中全部 $m \times n$ 个数按从小到大排成一列（允许重复，重复的数各算各的），求排在第 $k$ 位的那个数。

要什么：一个具体的数值。注意「第 $k$ 小」按可重复的多重集合计数，而不是去重后的第 $k$ 个不同值——2 在表里出现多次就要占多个名次。这是本题最容易读错的一句话。

约束透露的信号极其明确：$m$ 与 $n$ 都可达 $3 \times 10^4$，于是表里最多有 $9 \times 10^8$ 个数。这个规模下把整张表展开出来排序，光内存就要几个 GB，绝无可能；甚至连「用大小为 $k$ 的堆做多路归并」在 $k$ 接近 $9 \times 10^8$ 时也撑不住。一个「答案空间巨大、但答案本身是个数值」的问题，几乎必然指向二分答案：不去枚举第 $k$ 小是谁，而是猜一个值 $x$，问「表中小于等于 $x$ 的数有多少个」。

支撑二分的单调性藏在计数函数里：记 $f(x)$ 为表中不超过 $x$ 的元素个数，$x$ 越大 $f(x)$ 单调不减。这就把「找第 $k$ 小」转化成「找最小的 $x$ 使得 $f(x) \ge k$」，一个标准的下界二分。

而 $f(x)$ 能被快速算出，靠的是乘法表的结构而非它的排序：第 $i$ 行的元素是 $i, 2i, 3i, \dots, ni$，其中不超过 $x$ 的恰好有 $\min(n, \lfloor x / i \rfloor)$ 个。逐行累加即得 $f(x)$，只要 $O(m)$。

边界：$k = 1$ 时答案恒为 1；$k = m \times n$ 时答案是 $m \times n$；$m \times n$ 会超过 int 的舒适区（$9 \times 10^8$ 尚在范围内，但中间量如 left + right 会溢出），所以边界与计数都要用 64 位；行数与列数可以极不对称（如 $m = 1$），代码不能依赖方阵假设。

解法：值域二分 + 每行计数

核心思路

先看暴力：把 $m \times n$ 个乘积全部生成，排序后取第 $k$ 个。时间 $O(mn \log(mn))$、空间 $O(mn)$，在 $9 \times 10^8$ 个元素面前直接出局。稍好一点的是把每行看成一个有序序列做 $m$ 路归并、弹 $k$ 次堆，时间 $O(k \log m)$，但 $k$ 本身就能到 $9 \times 10^8$，仍然超时。瓶颈是同一个：这两种做法都试图把「第 $k$ 小」这个名次一步步数出来，而名次的规模和表的规模同阶。

换个方向：既然答案是一个数值，而数值的范围只有 $[1, m \times n]$，那就在值域上二分，而不是在元素上枚举。把判定问题设计成：
\[f(x) = \text{表中不超过 } x \text{ 的元素个数} = \sum_{i=1}^{m} \min\left(n,\ \left\lfloor \frac{x}{i} \right\rfloor\right)\]
这个式子的每一项都有直白的含义：第 $i$ 行的元素是 $i$ 的 1 到 $n$ 倍，满足 $i \cdot j \le x$ 的 $j$ 就是 $j \le x / i$，即 $j$ 最多取到 $\lfloor x/i \rfloor$；但 $j$ 又不能超过列数 $n$，所以取两者较小值。整个计数只用一遍行循环，$O(m)$，完全不需要展开任何元素。

$f$ 关于 $x$ 单调不减，于是判定「$f(x) \ge k$」也随 $x$ 单调：$x$ 小时为假，$x$ 大到某一点起恒为真。二分的目标就是这个分界点，也就是最小的满足 $f(x) \ge k$ 的 $x$。

这里必须论证一件事：这个分界点一定是表中真实存在的数，而不是某个凭空的整数。反证很短——设分界点为 $x_0$，则 $f(x_0) \ge k > f(x_0 - 1)$，两式相减说明恰好等于 $x_0$ 的元素至少有一个，所以 $x_0$ 在表中；同时它的名次区间 $[f(x_0-1)+1,\ f(x_0)]$ 覆盖了 $k$，所以它就是第 $k$ 小。这一步是「二分答案能直接返回边界值」的正确性根基，面试时值得主动说出来。

循环用左闭右闭区间上的经典下界写法，不变量是：答案始终落在 $[left, right]$ 内；且 $right$ 永远是一个已知满足 $f(right) \ge k$ 的候选（初始 $right = m \times n$ 时 $f = mn \ge k$ 成立），$left - 1$ 永远是一个已知不满足的位置。每轮取 mid，若 $f(mid) \ge k$ 就把 right 收到 mid（保留 mid 本身，因为它可能就是答案），否则 left = mid + 1（mid 已被排除）。区间每轮至少减半，left == right 时收敛到唯一候选。

解题步骤

把搜索区间初始化为 left = 1、right = (long) m * n。为什么下界是 1：表中最小的元素是 $1 \times 1 = 1$。为什么上界是 $m \times n$：最大元素就是右下角。为什么 m 要先强转 long：m * n 在 int 下虽然勉强不溢出，但先转 long 是零成本的保险，也让后续 mid 的算术全程在 64 位下进行。

循环条件写 left < right，取 mid = left + (right - left) / 2。为什么不用 (left + right) / 2：两者相加可能超过 int 上限；即便这里用了 long 不会溢出，减法式写法也是应该固化的习惯。为什么是 left < right 而不是 <=：这是「收敛到唯一解」的下界二分模板，退出时区间长度为 1，直接返回 left，不需要在循环里判断相等。

计算 countLE(mid)，与 k 比较。为什么比较用 >= k 而不是 == k：表中有大量重复值，$f(x)$ 会跳跃式增长，可能根本不存在使 $f(x)$ 恰好等于 $k$ 的 $x$；只有「第一个达到或超过 $k$」这个提法才是良定义的。

若 countLE(mid) >= k 则 right = mid，否则 left = mid + 1。为什么 right = mid 而不是 mid - 1：mid 自身满足条件，可能正是我们要找的最小者，丢掉它会错过答案。为什么 left = mid + 1 可以直接跳过 mid：mid 已被证明不满足 $f \ge k$，答案严格在它右侧。

countLE(x) 内部逐行累加 min(n, x / i)。为什么是整数除法：$\lfloor x/i \rfloor$ 正是第 $i$ 行中不超过 $x$ 的倍数个数，向下取整恰好对应「不超过」的语义。为什么要对 n 取 min：第 $i$ 行只有 $n$ 个元素，倍数再多也不存在。

循环结束返回 (int) left。为什么返回值一定是表中的元素：见核心思路里的反证——left 是使 $f$ 首次达到 $k$ 的位置，必然有元素恰好等于它。

以 具体用例 m = 3, n = 3, k = 5 走一遍。这张乘法表是

第 1 行 1 2 3，第 2 行 2 4 6，第 3 行 3 6 9。

全部 9 个元素排序后是 1, 2, 2, 3, 3, 4, 6, 6, 9，第 5 个是 3，这是我们要验证的目标。

初始 left = 1，right = 9。
第一轮：mid = 1 + (9 - 1) / 2 = 5。算 countLE(5)：第 1 行 $\min(3, \lfloor 5/1 \rfloor) = \min(3,5) = 3$（元素 1、2、3 都 $\le 5$）；第 2 行 $\min(3, \lfloor 5/2 \rfloor) = \min(3,2) = 2$（元素 2、4）；第 3 行 $\min(3, \lfloor 5/3 \rfloor) = \min(3,1) = 1$（元素 3）。合计 $3 + 2 + 1 = 6 \ge 5$，说明答案不超过 5，收缩右界：right = 5。
第二轮：区间 [1, 5]，mid = 1 + (5 - 1) / 2 = 3。算 countLE(3)：第 1 行 $\min(3,3) = 3$；第 2 行 $\min(3, \lfloor 3/2 \rfloor) = 1$（只有元素 2）；第 3 行 $\min(3,1) = 1$（元素 3）。合计 $3 + 1 + 1 = 5 \ge 5$，right = 3。注意此处 $f(3) = 5$ 恰好等于 $k$，但仍不能立即返回——必须继续二分确认 3 是最小的达标值，否则若某个更小的 $x$ 也满足 $f(x) \ge 5$，答案就该是那个更小的数。
第三轮：区间 [1, 3]，mid = 1 + (3 - 1) / 2 = 2。算 countLE(2)：第 1 行 $\min(3,2) = 2$（元素 1、2）；第 2 行 $\min(3,1) = 1$（元素 2）；第 3 行 $\min(3, \lfloor 2/3 \rfloor) = \min(3,0) = 0$（第 3 行最小元素是 3，已超过 2）。合计 $2 + 1 + 0 = 3 < 5$，说明答案严格大于 2，left = 2 + 1 = 3。
此时 left == right == 3，循环退出，返回 3，与手工排序的结果一致。

再确认一下 3 为什么是第 5 小：$f(2) = 3$ 说明有 3 个元素 $\le 2$，$f(3) = 5$ 说明有 5 个元素 $\le 3$，于是值为 3 的元素占据了第 4、第 5 两个名次，$k = 5$ 落在其中。

代码实现

class Solution {
    // 值 x 作为阈值时，可以快速算出表中有多少个数不超过 x，用这个计数函数做二分查找。
    public int findKthNumber(int m, int n, int k) {
        long left = 1;
        long right = (long) m * n;
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (countLE(mid, m, n) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return (int) left;
    }

    private long countLE(long x, int m, int n) {
        long total = 0;
        for (int i = 1; i <= m; i++) {
            total += Math.min(n, (int) (x / i));
            if (total > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            }
        }
        return total;
    }
}

func findKthNumber(m int, n int, k int) int {
    // 值 x 作为阈值时，可以快速算出表中有多少个数不超过 x，用这个计数函数做二分查找。
    left := int64(1)
    right := int64(m) * int64(n)
    for left < right {
        mid := left + (right-left)/2
        if countLE(mid, m, n) >= int64(k) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return int(left)
}

func countLE(x int64, m int, n int) int64 {
    var total int64
    for i := 1; i <= m; i++ {
        c := int(x / int64(i))
        if c > n {
            c = n
        }
        total += int64(c)
    }
    return total
}

复杂度分析

时间复杂度：$O(m \log(mn))$。凭什么：值域长度是 $m \times n$，每轮二分把区间对折，因此迭代次数是 $O(\log(mn))$，在 $m = n = 3 \times 10^4$ 时约 30 轮；每轮调用一次 countLE，它只做 $m$ 次除法与取最小，是 $O(m)$。两者相乘约 $9 \times 10^5$ 次基本运算，与暴力展开的 $9 \times 10^8$ 相差三个数量级。

空间复杂度：$O(1)$。凭什么：全程只有 left、right、mid、total 几个 64 位标量，乘法表从未被真正物化到内存里——这正是二分答案相对于排序法和堆归并法的决定性优势，后两者分别需要 $O(mn)$ 与 $O(m)$ 的额外空间。

关键点总结

答案空间小、候选元素多时，就在答案上二分而不是在元素上枚举。识别信号是「问某个第 $k$ 大/小、最小的最大值、最大的最小值」，且答案的取值范围能被一个简单区间框住。本题的元素有 $9 \times 10^8$ 个，但答案只可能落在 $[1, mn]$ 这一个区间里。

二分答案的核心是把最优化问题改写成单调的判定问题。这里的判定是「$f(x) \ge k$」，$f$ 单调不减保证了「假假假真真真」的结构，二分才有意义。写题时先花时间确认单调性，比先写循环重要得多。

计数函数要利用结构而非利用有序。$f(x) = \sum \min(n, \lfloor x/i \rfloor)$ 用的是「第 $i$ 行是 $i$ 的倍数」这条代数性质，压根没有依赖行内或列内的有序性；这也是为什么它能做到 $O(m)$ 而不是 $O(m \log n)$（逐行二分）。

二分出的边界值一定是真实存在的元素，需要一句反证来支撑：$f(x_0) \ge k > f(x_0-1)$ 意味着恰好等于 $x_0$ 的元素至少有一个。没有这句话，「为什么可以直接返回 left」就是悬空的。

值域二分的三件套要固化成肌肉记忆：while (left < right)、mid = left + (right-left)/2、命中时 right = mid 而非 mid - 1。这套模板求的是下界（第一个为真的位置），求上界时才需要换成另一套。

面试视角：这题的失分点通常不在代码，而在讲不清「为什么比较用 $\ge k$ 而不是 $= k$」和「为什么答案必然在表中」。建议按「暴力排序不可行 → 堆归并仍受限于 $k$ → 值域二分 → 计数函数如何 $O(m)$ 得到 → 边界值必在表中」的顺序讲，最后主动补一句「同一套模板可以直接迁移到 378、719、878」，展示题型识别能力。

易错点总结

错误写法：判定写成 countLE(mid) == k 就返回 mid → 用例 m = 3, n = 3, k = 4，正确答案是 3，但不存在任何 $x$ 使 $f(x) = 4$（$f(2) = 3$，$f(3) = 5$），二分会一路走到区间为空也没能返回，逻辑彻底失效。表中有重复值时 $f$ 是跳跃的，只能用 $\ge$。

错误写法：right = mid - 1 → 用例 m = 3, n = 3, k = 5，第二轮 mid = 3 满足 $f(3) = 5 \ge 5$，若把 right 收到 2，正确答案 3 被排除在区间外，最终返回 2。命中条件时必须保留 mid 本身。

错误写法：mid = (left + right) / 2 且 left、right 用 int → 用例 m = 30000, n = 30000, k = 900000000，right = 9 × 10^8，某轮 left + right 超过 int 上限 $2147483647$ 溢出为负，mid 变成负数，countLE 全行返回 0，二分方向彻底反转。

错误写法：right 初始化为 m * n 而两个操作数都是 int → 同上用例，m * n 本身尚未溢出（$9 \times 10^8 < 2^{31}$），但把这个习惯带到 $m = n = 10^5$ 的变形题上会立刻溢出；应当写 (long) m * n，强转必须作用在乘法之前。

错误写法：countLE 里忘记对 n 取 min，直接写 total += x / i → 用例 m = 3, n = 2, k = 3（表为 1 2 / 2 4 / 3 6，排序后 1,2,2,3,4,6，第 3 小是 2），计算 countLE(2) 时第 1 行得 $\lfloor 2/1 \rfloor = 2$ 正确，但计算 countLE(4) 时第 1 行得 4，而第 1 行只有 2 个元素，计数被高估，二分收敛到偏小的值。

错误写法：countLE 里用浮点除法 (int)(x / (double) i) → 用例 x = 3, i = 3，浮点结果可能是 0.9999999999999999，取整后得 0 而不是 1，少数一个元素，计数偏小导致答案偏大。整除语义必须用整数除法表达。

错误写法：把「第 $k$ 小」理解成去重后的第 $k$ 个不同值 → 用例 m = 3, n = 3, k = 5，去重后的序列是 1,2,3,4,6,9，第 5 个是 6，而正确答案是 3。题面按可重复的多重集合计名次。

错误写法：外层循环写成 while (left <= right) 却仍在命中时 right = mid → 任意用例下，当 left == right 且该点满足条件时，right = mid 不改变区间，循环条件恒成立，程序死循环。right = mid 必须配 left < right。

错误写法：countLE 的行循环从 i = 0 开始 → 用例任意，$i = 0$ 时 x / i 触发除零异常（Go 中直接 panic）。乘法表的行列下标都从 1 开始，这是题面定义的一部分。

错误写法：为了省时间只对前 $\min(m, \sqrt{x})$ 行计数，认为后面的行贡献都是 0 → 用例 m = 5, n = 5, x = 10，第 4 行贡献 $\lfloor 10/4 \rfloor = 2$、第 5 行贡献 2，都不为 0；只有当行号超过 $x$ 时贡献才归零，剪枝条件应是 i > x 而不是 $\sqrt{x}$。

相似题目

题目	难度	考察点
378. 有序矩阵中第 K 小的元素	中等	矩阵只保证行列有序而无代数结构，计数只能靠从左下角走阶梯，$O(n)$ 而非公式
719. 找出第 K 小的数对距离	困难	同为「第 K 小」值域二分，但计数函数要先排序再用滑动窗口统计满足条件的数对
878. 第 N 个神奇数字	困难	计数靠容斥与最小公倍数，且答案巨大必须全程取模，二分上界要自己估
1201. 丑数 III	中等	三个因子的容斥计数，重点是别把同时被整除的数重复计入
786. 第 K 个最小的质数分数	中等	值域是实数区间，二分时还要顺带记录取到最大分数的那一对下标
875. 爱吃香蕉的珂珂	中等	二分「速度」这个不在原数据中的量，判定函数是耗时是否超限，最小化最大值的入门
1011. 在 D 天内送达包裹的能力	中等	二分运载能力，判定要按顺序贪心装箱，下界必须取单件最大重量而非 1
410. 分割数组的最大值	困难	二分子数组和的上限，判定是贪心分段计数，也可用 DP 解，是两种范式的分水岭
1482. 制作 m 束花所需的最少天数	中等	二分天数，判定要扫描连续段并处理「无解直接返回 -1」的前置检查
1552. 两球之间的磁力	中等	最大化最小间距，判定方向与本题相反，收敛的是上界而不是下界
4. 寻找两个正序数组的中位数	困难	同样是找第 K 小，但二分的是分割位置而非值域，要求 $O(\log(m+n))$
373. 查找和最小的 K 对数字	中等	$k$ 规模较小时堆归并才是正解，与本题形成「何时二分、何时用堆」的对照