668. 乘法表中第k小的数
难度困难196收藏分享切换为英文接收动态反馈
几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？
给定高度m 、宽度n 的一张 m * 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, m * n] 之间。
通过次数10,499提交次数19,300
题解：
思路分析： 这道题可能有人会想着先构造出这个乘法表，然后再去搜索，但这样是行不通的， 因为m、n的取值可能非常大，非常耗内存。首先我们知道在m、n的乘法表中取值范围为[1, m * n]， 那么我们可不可以使用使用二分搜索呢？ 首先观察乘法表我们会发现，由于构造关系，决定了他每一行都是递增的。 如果我们需要在第i行中寻找不大于num的个数，我们只要min(num / i, n)， 其中（i是这一行的行号，n是矩阵的列数）num / i代表的是如果num也在第i行， 它存在的列数，所以只要取最小值就是第i行不大于num的个数。 （比如例题1中，我们需要知道第2行，不大于4的个数，min(4 / 2, 3) == 2个（就是2， 4）） 那么如果我们需要确定这个乘法表中不大于num的个数就非常简单了，我们只要将每一行 不大于num的个数累加即可。（比如例题1中，我们需要知道乘法表中不大于4的个数， 第一行3个、第二行2个，第三行1个） 现在我们就可以使用二分搜索了，初始化left = 1， right = n * m + 1， mid = （left + right） / 2，在m，n的乘法表中寻找不超过mid的个数。 --------------------- 作者：hestyle 来源：CSDN 原文：https://blog.csdn.net/qq_41855420/article/details/89397884 版权声明：本文为博主原创文章，转载请附上博文链接！
如何使用二分法找到第一个满足==k的值呢？当小于的时候，直接left=mid+1，寻找下一个；当大于等于条件的时候，right=mid，不断往下压，当left==right的时候，就找到了。
代码部分：
class Solution {
int countNotbiggeThanTarget(int m,int n,int target)
{
int sum=0;
for(int i=1;i<=m;i++)
{
sum+=min(target/i,n);
}
return sum;
}
public:
int findKthNumber(int m, int n, int k) {
int left=1,right=m*n+1;
int count=0;
while(left
执行结果：
通过
显示详情
添加备注
执行用时：8 ms, 在所有 C++ 提交中击败了99.39%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了86.20%的用户
通过测试用例：70 / 70
