题目描述
这是 LeetCode 上的 668. 乘法表中第k小的数 ，难度为 困难。
Tag : 「二分」、「计数」
几乎每一个人都用 乘法表，但是你能在乘法表中快速找到第 $k$ 小的数字吗？
给定高度 $m$ 、宽度 $n$ 的一张 $m \times n$ 的乘法表，以及正整数 $k$，你需要返回表中第 $k$ 小的数字。
例 1：
输入: m = 3, n = 3, k = 5输出: 3解释: 乘法表:1 2 32 4 63 6 9第5小的数字是 3 (1, 2, 2, 3, 3).
例 2：
输入: m = 2, n = 3, k = 6输出: 6解释: 乘法表:1 2 32 4 6第6小的数字是 6 (1, 2, 2, 3, 4, 6).
注意：
$m$ 和 $n$ 的范围在 $[1, 30000]$ 之间。
$k$ 的范围在 $[1, m \times n]$ 之间。
二分 + 计数判定
由于 $n$ 和 $m$ 的数据范围都是 $3 \times 10^4$，总数本身就超过了 $10^7$，我们考虑线性复杂度往下的对数复杂度。
题目要求我们求一维展开有序序列中的第 $k$ 小的数，问题本身具有「二段性」：
答案右边的每个数均 满足「其在一维展开有序序列中左边数的个数大于等于 $k$ 个」
答案左边的每个数均 不满足「其在一维展开有序序列中左边数的个数大于等于 $k$ 个」
我们考虑如何进行「二分答案」: 假设当前我们二分到的值是 $mid$，对于乘法表中的每行和每列均是单调递增，我们可以通过累加统计 每行/每列 中比 $mid$ 小的数，记作 $a$，累加统计 每行/每列 中等于 $mid$ 的数，记作 $b$，那么 $cnt = a + b$ 即是整个乘法表中小于等于 $mid$ 的数的个数，再通过 $cnt$ 和 $k$ 的大小关系来指导左右指针的变化。
具体的，假设我们通过枚举行来统计 $a$ 和 $b$，当前枚举到的行号为 $i$（行号从 $1$ 开始），该行的最大数为 $i \times m$：
若 $i \times m < mid$，整行都是小于 $mid$ 的数，直接在 $a$ 基础上累加 $m$；
若 $i \times m >= mid$，根据 $mid$ 是否存在于该行进行分情况讨论：
$mid$ 能够被 $i$ 整除，说明 $mid$ 存在于该行，那么比 $mid$ 小的数的个数为 $\frac{mid}{i} - 1$，将其累加到 $a$，同时对 $b$ 进行加一；
$mid$ 不能够被 $i$ 整除，说明 $mid$ 不存在于该行，那么比 $mid$ 小的数的个数为 $\frac{mid}{i}$，将其累加到 $a$。
一些细节：由于乘法表具有对称性，我们统计时可以对 行和列 中较小的一方进行遍历。
代码：
class Solution { int n, m, k; public int findKthNumber(int _m, int _n, int _k) { n = Math.min(_m, _n); m = Math.max(_m, _n); k = _k; int l = 1, r = m * n; while (l < r) { int mid = l + r >> 1, cnt = getCnt(mid); if (cnt >= k) r = mid; else l = mid + 1; } return r; } int getCnt(int mid) { int a = 0, b = 0; for (int i = 1; i <= n; i++) { if (i * m < mid) { a += m; } else { if (mid % i == 0 && ++b >= 0) a += mid / i - 1; else a += mid / i; } } return a + b; }} 时间复杂度：$O(\min(n, m) \times \log{nm})$
空间复杂度：$O(1)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.668 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
原文：https://juejin.cn/post/7098892656813539365