668. 乘法表中第k小的数

大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

小时候我们都背过“九九乘法表”对吧？今天这个题目给出的乘法表不是 的，而是 的。

要我们求这个乘法表中第 小的数字。

下面是一个 的乘法表：

解题方法

分析

要求“第 小的数字 ” 。

如果给出的是一维数组，那么这个问题就是 经典问题，参考题目 215. 数组中的第K个最大元素。

如果给出的是一个行列都递增的二维矩阵，那么也是个经典问题，可以从左下角或者右下角开始搜索，参考题目
240. 搜索二维矩阵 II。

其实乘法表也是一个行列都递增的二维矩阵，但是由于 的范围很大()，单单把乘法表构造出来 的时间复杂度会超时。

因此我们必须要用更优的算法。

二分查找

二分查找说白了就是「尝试」，只不过是更加聪明的尝试。

首先，给了一个 乘法表的二维矩阵，我们其实能很快地找到矩阵中有多少个数字小于等于 。

先看下图：

由于第 行的数字分别是 ，因此这一行小于等于 的数字个数为 。

那么矩阵中小于等于的数字个数 各行的累加，即 个。

注意求和公式伴随着 的增加，也是单调递增的。

很好理解，乘法表中小于等于 的数字个数，肯定随着 的增加而增加。

这题希望得到出什么呢？

希望得到 时的 值。

含义就是得到乘法表中小于等于 的数字个数恰好为 时， 的值。

这个 怎么求出来呢？就是用「二分法」去搜索尝试。

大家应该都玩过「猜数字」的游戏，玩家报一个数字，裁判告诉你猜的这个数字是「大了」还是「小了」。然后玩家就可以缩小下次猜数字的区间。这就是二分法的实际运用。

这个题也是一样，我们尝试某一个 ，相当于问：“乘法表中小于等于 的数字个数是 吗？”

根据 的值，我们可以知道 是「大了」还是「小了」；然后就知道下一步是缩小 还是放大 。

我们这题在区间 上进行二分搜索，找到符合条件的最小数字。

需要注意的是，本题中的搜索空间中可能有多个符合条件的数字。因此我们需要搜索到符合条件的并且最小的数字。

为什么呢？

因为 区间的数字并不一定都在乘法表中存在，所以我们可能猜测了一些无效的且符合要求的数字。我们找到符合要求的且最小的数字一定在乘法表中。

比如下面的例子，我们查找小于等于 $5$ 的数字有 $6$ 个，和小于等于 $4$ 的结果个数相等。但是数字 $5$ 并不在乘法表中，因此我们必须要找到符合要求并且最小的数字，即 $4$。

用动图演示一下这个过程：

代码

class Solution {
    public:
    int findKthNumber(int m, int n, int k) {
        int left = 1;
        int right = m * n;
        // [left, right]
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (count(m, n, mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    // 统计乘法表中有多少个小于等于 k 的数目
    int count(int m, int n, int k) {
        int res = 0;
        // 统计每行小于等于 k 的数目
        for (int i = 1; i <= m; ++i) {
            res += min(k / i, n);
        }
        return res;
    }
};

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

    // 统计乘法表中有多少个小于等于 k 的数目
    int count(int m, int n, int k) {
        int res = 0;
        // 统计每行小于等于 k 的数目
        for (int i = 1; i <= m; ++i) {
            res += Math.min(k / i, n);
        }
        return res;
    }
}

复杂度

• 时间复杂度：。
• 空间复杂度：$O(1)$。

  总结

1. 本题是二分查找的应用，可以多看看我的题解理解一下这个过程。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。