2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

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).

注意：

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

方法一：二分搜值

还记得240. 搜索二维矩阵 II 这道题吗。这道题利用有序矩阵的特点，通过2个指针来排除答案。

这题就会用和240一模一样的方法，不断缩小我们的二分搜值的答案，推算出比k小的乘法表里的所有数字。

乘法表的特性很容易看到，每行从小到大递增，每列从小到大也在递增。

我们可以从左下角或者右上角触发，不断筛选我们的二分答案。得出答案后，就是很简单的二分，属实hard里的水题。

几乎一模一样的题目还有378. 有序矩阵中第 K 小的元素

只是不需要i*j了，单纯搜值就可以。其他代码几乎原封不动。

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int l = 0, r = m * n;
        auto check = [&](int mid) {
            int i = m, j = 1;
            int res = 0;
            while (i >= 1 && j <= n ) {
                if (i * j <= mid) {
                    res += i;
                    j++;
                } else {
                    i--;
                }    

            }
            return res >= k;
        };
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return l;
    }
};