[二分查找] 乘法表中第k小的数
二分查找系列专题 LeetCode668
题目描述
几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？
给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。
示例:
输入: m = 3, n = 3, k = 5
输出: 3
解释:
乘法表:
1 2 3
2 4 6
3 6 9
第5小的数字是 3 (1, 2, 2, 3, 3).
注意
-
m和n的范围在 [1, 30000] 之间。 -
k的范围在 [1, m * n] 之间。
题解
二分查找系列是我搜罗的二分查找系列的难题集合，因此今后不再讨论简单的暴力解法（无法AC且没太大意义）。
我点开这道题，它没有时间复杂度要求，方方正正的乘法表仿佛在告诉我用遍历去做。我想这个困难题不可能这么没有营养，我绞尽脑汁，仔细看了前人留下来的题解，才恍然大悟，大家都告诉我要用“二分”。
这个题和一般的二分法思路还稍有区别，二分的对象是乘法表里面的乘积。比如上面的示例中给出的3行3列的乘法表，最小值为1，最大值为3*3=9，那二分的初始边界就是1和9，详细的搜索步骤为：
-
令 left=1，right=9，求得mid=5；计算乘法表中小于等于5的数字的个数为6，现要求第5小的数字，显然这个数字应该在[1, 5]之间； -
令 left=1，right=5，求得mid=3；计算乘法表中小于等于3的数字的个数为5，现要求第5小的数字，显然这个数字应该在[1, 3]之间； -
令 left=1，right=3，求得mid=2；计算乘法表中小于等于2的数字的个数为3，现要求第5小的数字，显然这个数字应该在[3, 3]之间； -
left == right == 3，查询结束，返回3。
问：以上的思路很清晰吧，那么如何计算乘法表中小于等于target的数字的个数呢？
观察得到第i行的数字规律为 ，因此从上往下依次遍历每一行，按照如下方式计算：
// mid / i 表示第i行中小于等于mid的数字的个数，n表示列数
cnt += min(mid / i, n);
最终代码如下：
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n;
while (left < right) {
int mid = left + (right - left) / 2;
int cnt = 0;
for (int i = 1; i <= m; i++) {
cnt += min(n, mid / i);
}
if (cnt >= k) right = mid;
else left = mid + 1;
}
return left;
}
};