1.题目描述

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

2.思路

2.1 代码

这道题看到第 k 小的数字，首先考虑到使用优先级队列进行解答，但是很不幸提交代码提示超过时间限制，看来题目限制了时间复杂度控制在以内。

class Solution {
    public int findKthNumber(int m, int n, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                queue.add(i * j);
            }
        }
        int ans = 0;
        while (k > 0) {
            ans = queue.poll();
            k--;
        }
        return ans;
    }
}

因此需要重新寻找思路。通过观察示例可以看出第一行和第一列从 1 开始依次递增，并且每一列的值为该行第一个数的 1 倍、2 倍、3 倍……并且整个二维表的取值范围为 [1, m*n] 。在已知范围并且范围内局部有序的情况下寻找某一个数，考虑使用二分查找法进行解答。

1      2      3      4
2      4      6      8
3      6      9      12
4      8      12     16

使用二分查找法的思路如下：

• 先找到中点 mid，然后对 mid 进行处理

• 统计整个二维表中小于 mid 的个数，这里统计个数需要对每一行进行遍历，并且统计每一行小于等于mid的个数：

  1. 如果 mid 大于等于该行最后一个数时，则加上该行每一个数字，即列数；
  2. 如果 mid 小于该行最后一个数时，则加上 mid 除以该行第一个数字（因为行内数字成倍增长）

• 如果小于 mid 的数字总数小于 k，表示 k 在右范围，让 left 等于 mid+1 继续循环

• 如果小于 mid 的数字总数大于 k，表示 k 在左范围，让 right 等于 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) / 2;
            int lessThanMid = 0;
            for (int i = 1; i <= m; i++) {
                lessThanMid += i * n <= mid ? n : mid / i;
            }
            if (lessThanMid < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

2.2 测试结果

通过测试

测试结果

3.总结

• 使用优先级队列提交代码会提示超时
• 根据二维表特性使用二分搜索法进行解答
• 每次循环获取 mid 之后需要统计二维表中小于 mid 的数的个数，然后根据个数确定下一轮循环的范围