关注公众号【算法码上来】，每日算法干货马上就来！
题目链接
题目描述
几乎每一个人都用乘法表。但是你能在乘法表中快速找到第 $k$ 小的数字吗？
给定高度 $m$、宽度 $n$ 的一张 $m \times n$ 的乘法表，以及正整数 $k$，你需要返回表中第 $k$ 小的数字。
示例1
输入：
m = 3, n = 3, k = 5
输出：
3
解释：
乘法表:
1 2 3
2 4 6
3 6 9
第5小的数字是 3 (1, 2, 2, 3, 3).示例2
输入：
m = 2, n = 3, k = 6
输出：
6
解释：
乘法表:
1 2 3
2 4 6
第6小的数字是 6 (1, 2, 2, 3, 4, 6).说明：
- $m$ 和 $n$ 的范围在 $[1, 30000]$ 之间。
- $k$ 的范围在 $[1, mn]$ 之间。
题解
二分法
因为 $mn$ 数量级是 $9 \times 10^8$ 级别的，所以显然不能直接枚举，要想一个对数级别的算法。
对数级别首先想到的肯定是二分了，我们二分第 $k$ 小的数 $mid$ ，然后求出乘法表中小于等于 $mid$ 的数的数量 $cnt$ 。如果发现 $cnt \le mid$ ，那就说明这个答案太大了，还可以继续缩小。否则的话答案太小了，得增大一点。
那么对于枚举的答案 $mid$ 来说，如何找到乘法表中有多少小于等于它的数呢？我们可以直接从 $1$ 开始枚举，和 $1$ 相乘并且结果小于等于 $mid$ 的数有 $mid$ 个，当然还有个 $n$ 的限制，所以是 $\min{(mid, n)}$ 个。然后和 $2$ 相乘并且结果小于等于 $mid$ 的数有 $\min{(\left\lfloor\frac{mid}{2}\right\rfloor, n)}$ 个。依此类推下去，最终和 $m$ 相乘并且结果小于等于 $mid$ 的数有 $\min{(\left\lfloor\frac{mid}{m}\right\rfloor, n)}$ 个。
所以最终小于等于 $mid$ 的个数 $cnt$ 就可以计算为：
$$
\sum_{i=1}^{m}{\min{\left(\left\lfloor\frac{mid}{i}\right\rfloor, n\right)}}
$$
二分法+优化
当然这题计算还可以进行一些优化。
首先第 $k$ 小的数是一定小于等于 $k$ 的，所以我们的二分上界可以定为 $k$ 。
其次注意到当 $i > mid$ 之后，个数一定是 $0$，所以 $i$ 只需要枚举到 $\min{(mid, m)}$ 就行了。
然后当 $i \le \left\lfloor\frac{mid}{n}\right\rfloor$ 时，有 $\min{\left(\left\lfloor\frac{mid}{i}\right\rfloor, n\right)} = n$，所以这部分的求和结果就是 $n\left\lfloor\frac{mid}{n}\right\rfloor$ 。所以 $cnt$ 又可以写为：
$$
n\left\lfloor\frac{mid}{n}\right\rfloor + \sum_{i=\left\lfloor\frac{mid}{n}\right\rfloor+1}^{\min{(mid, m)}}{\left\lfloor\frac{mid}{i}\right\rfloor}
$$
最后，对于某个 $i = t$ ，我们会发现如果 $i$ 慢慢增大，某一段连续区间内 $\left\lfloor\frac{mid}{i}\right\rfloor$ 的值都是不会变的。而 $i$ 最大可以增大到 $\left\lfloor\frac{mid}{\left\lfloor\frac{mid}{t}\right\rfloor}\right\rfloor$，那么这一段区间内的求和就可以直接算出来：
$$
\left\lfloor\frac{mid}{t}\right\rfloor \left(\left\lfloor\frac{mid}{\left\lfloor\frac{mid}{t}\right\rfloor}\right\rfloor-t+1\right)
$$
接着令 $i$ 直接跳转到 $\left\lfloor\frac{mid}{\left\lfloor\frac{mid}{t}\right\rfloor}\right\rfloor + 1$ 就可以了，这样就不用慢慢加 $1$ 计算了。要特别注意的是最后不能超过 $m$ 。
理论上这样的计算复杂度是更低的，但是实际运行中速度还不如不加最后一步优化，可能原因是除法操作次数太多了，反而总的操作次数超过了直接遍历计算。
代码
二分法（c++）
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int l = 1, r = m*n;
while (l < r) {
int mid = l+((r-l)>>1);
if (enough(mid, m, n, k)) r = mid;
else l = mid+1;
}
return l;
}
bool enough(int x, int m, int n, int k) {
int cnt = 0;
for (int i = 1; i <= m; ++i) {
cnt += x/i<n?x/i:n;
}
return cnt >= k;
}
};二分法+优化（c++）
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int l = 1, r = k;
while (l < r) {
int mid = l+((r-l)>>1);
if (enough(mid, m<mid?m:mid, n<mid?n:mid, k)) r = mid;
else l = mid+1;
}
return l;
}
bool enough(int x, int m, int n, int k) {
int cnt = n*(x/n), d = 0;
for (int i = (x/n)+1; i <= m; i = d+1) {
d = x/(x/i);
cnt += (x/i)*((d<m?d:m)-i+1);
}
return cnt >= k;
}
};二分法（python）
class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
def enough(x, m, n, k):
cnt = 0
for i in range(1, m+1):
cnt += x//i if x//i<n else n
return cnt >= k
l, r = 1, m*n
while l < r:
mid = l+((r-l)>>1)
if enough(mid, m, n, k): r = mid
else: l = mid+1
return l二分法+优化（python）
class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
def enough(x, m, n, k):
cnt, i, d = n*(x//n), x//n+1, 0
while i <= m:
d = x//(x//i)
cnt += (x//i)*((d if d<m else m)-i+1)
i = d+1
return cnt >= k
l, r = 1, k
while l < r:
mid = l+((r-l)>>1)
if enough(mid, m if m<mid else mid, n if n<mid else mid, k): r = mid
else: l = mid+1
return l
