668. 乘法表中第k小的数

1.题目

几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？
给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。

输入: m = 3, n = 3, k = 5
输出: 3
解释: 
乘法表:
1    2    3
2    4    6
3    6    9
第5小的数字是 3 (1, 2, 2, 3, 3).

输入: m = 2, n = 3, k = 6
输出: 6
解释: 
乘法表:
1    2    3
2    4    6
第6小的数字是 6 (1, 2, 2, 3, 4, 6).

注意：

• m 和 n 的范围在 [1, 30000] 之间。
• k 的范围在 [1, m * n] 之间。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

最容易想到的就是暴力获得所有乘积的结果然后排序获得第k小的数字，但看到这个是个困难题就应该知道此路不通，成功超时。所以，我们需要换一种想法。考虑乘法表中的数值x是乘法表中第几小的数字，考虑什么样的x才能满足第k小的这个条件。对于乘法表中的一个数x来说，第i行小于等于x的个数为min（x/i， n),将每行求和即可获得x是乘法表中第几小的结果。具体来说，当x/i>n时，第i行小于等于x的个数为n，当x/i<n时，第i行小于等于x的个数为x/i.对于x来说我们可以知道其范围为[1,m*n]也就是我们需要在这个范围内去寻找满足条件的x，可以通过二分法求解。这里还需要注意一个细节。在乘法表中，假设满足第k小的数为x1，第k+1小的数为x2，其中的范围为(x1,x2)在二分过程中都可以出现，因为其在乘法表中也为第k小的数，如何避免这些并为出现在乘法表中的数呢，在二分过程中，我们遇到满足条件的数时，并不会直接返回该数，而是继续二分，找到最小的满足小于等于x的个数为k的数，该数一定会在乘法表中，这样就避免了返回乘法表中不存在的数的情况。

3.代码

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int left = 1, right = m*n;
        while(left < right)
        {
            int mid = left + (right - left)/2;
            int count = mid/n*n;
            for(int i = mid/n+1; i <= m; i++)
            {
                count = count + (mid/i);
            }
            //cout << count << endl;
            if(count >= k)
                right = mid;
            else
                left = mid+1;
        }
        return left;
    }
};