力扣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;
        }
    };