解题思路
【LeetCode 668. 乘法表中第k小的数】通过二分法对1到m*n之间的数进行吗枚举，之后要找乘法表中有多少个数比这个数小。
要么一行的所有数都比这个数小，要么有mid/n个数比这个数小。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m3AcuxEL-1614520107747)(https://cdn.acwing.com/media/article/image/2021/02/28/39383_94454b8c79-4.png)]
代码
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>1;
if(check(m,n,mid)>=k) r=mid;
else l=mid+1;
}
return r;
}
};
推荐阅读
- 算法题-字符串3.17
- LeetCode编程题解法汇总|力扣解法汇总720-词典中最长的单词
- 蓝桥杯|蓝桥杯-新枚举方法应用
- 学习记录|393. UTF-8 编码验证
- leetcode|leetcode 543（二叉树的直径）
- 557.反转字符串中的单词III（JS）——leetCode
- leetcode刷题记录|移动零——LeetCode283题
- leetcode刷题记录|反转字符串——LC344题
- leetcode刷题记录|两数之和II - 输入有序数组——LC167题（中等难度）