668. 乘法表中第k小的数

[MyLinChi]

问题

几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第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.com/problems/kth-smallest-number-in-multiplication-table
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

求解

法一：（内存超出限制）
二分法，思路跟378题一样，每次二分时统计矩阵中<=mid的数。

class Solution {
private int[][] mp;

    private boolean isInLeft(int mid, int m, int n, int k) {
        int i = m;
        int j = 1;
        int sum = 0;
        for (; i > 0 && j <= n; ) {
            if (mp[i][j] > mid) {
                --i;
            } else {
                sum += i;
                ++j;
            }
        }
        return sum >= k;
    }

    public int findKthNumber(int m, int n, int k) {
        mp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                mp[i][j] = i * j;
            }
        }
        int left = 1;
        int right = mp[m][n];
        for (; left < right; ) {
            int mid = left + ((right - left) >> 1);
            if (isInLeft(mid, m, n, k)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

法二：
乘法表中的数据可以由行*列得到，不需要提前算出。

class Solution {
    private boolean isInLeft(int mid, int m, int n, int k) {
        int i = m;
        int j = 1;
        int sum = 0;
        for (; i > 0 && j <= n; ) {
            if (i*j > mid) {
                --i;
            } else {
                sum += i;
                ++j;
            }
        }
        return sum >= k;
    }

    public int findKthNumber(int m, int n, int k) {
        int left = 1;
        int right = m*n;
        for (; left < right; ) {
            int mid = left + ((right - left) >> 1);
            if (isInLeft(mid, m, n, k)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
}