力扣668.乘法表中第k小的数
力扣668.乘法表中第k小的数
-
二分查找
- 是否有k个比mid小的数
-
class Solution {public:int findKthNumber(int m, int n, int k) {auto check = [&](int mid) -> bool{int res=0;int row = 1,col = n;while(row <= m){if(row * col <= mid){res += col;if(res >= k) return false;row ++;}else col --;}return true;};int l = 1,r = n * m;while(l<r){int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}return r + 1;}};