668. 乘法表中第k小的数

668. 乘法表中第k小的数

同样，二话不说写个暴力，用两个一维数组来存储行和列，用一个vector来存储乘法表中的每个数，sort排个序输出k位置的数即可，

意料之中，超时，且还是最后一组数据超时！！害### 然后用了二分来写，最小的是1，最大的数是m*n,那么取个mid，

在乘法表里记录每行有多少个数小于等于mid的，经发现可得每行小于等于mid的数为 \(min(mid / i, n)\) ,然后累加判断和k比较

• 如果大于了k，说明该mid的这个数已经够了范围，甚至在范围之外了，只要再左边找即可
• 如果小于了k，则说明mid这个数还不够第k小的数，需要继续向右找

代码如下：

class Solution {
public:
        bool check(int m,int n,int mid,int k)
        {
            int cnt=0;
            for(int i=1;i<=m;i++)
            {
                cnt+=min(mid/i,n);
            }
            return cnt<k;
        }
        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))
                L=mid+1;
            else
                R=mid-1;
        }
        
        return L;
    }
};

668. 乘法表中第k小的数

原文：https://www.cnblogs.com/Vampire6/p/13196173.html