解题思路
通过二分法对1到m*n之间的数进行吗枚举,之后要找乘法表中有多少个数比这个数小。
要么一行的所有数都比这个数小,要么有mid/n个数比这个数小。
代码
class Solution {
public:
int check(int m,int n,int mid) //统计一共有多少个数比mid值小
{
int res=0;
for(int i=1;i<=m;i++)
{
res+=min(n,mid/i); //一行的所有数的个数和mid/n个数,二者中取最小值
}
return res;
}
int findKthNumber(int m, int n, int k) {
int l=1,r=m*n;
while(l<r)
{
int mid=(l+r)>>1;
if(check(m,n,mid)>=k) r=mid;
else l=mid+1;
}
return r;
}
};