668. 乘法表中第k小的数

题目

几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？

给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。

例 1：

输入: m = 3, n = 3, k = 5
输出: 3
解释:
乘法表:
1 2 3
2 4 6
3 6 9

第5小的数字是 3 (1, 2, 2, 3, 3).

例 2：

输入: 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

和「378. 有序矩阵中第 K 小的元素」同样的思路，只是这个题没有实际的矩阵，而且这个题每两个相邻的数之间差值是确定的，不需要按378一样走2n步去确定不大于mid的数有多少，mid除以行数就是该行不大于mid的数目。

代码

class Solution {
    public int findKthNumber(int m, int n, int k) {
        int left = 1;
        int right = m * n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int cnt = 0;
            // 累加每一行有多少数不大于mid
            // 从mid+1开始，后面就没有小于等于mid的数了，因此最多只需遍历到mid行
            for (int i = 1; i <= Math.min(m, mid); i++) {
                cnt += Math.min(mid / i, n);
            }
            if (cnt < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}