1.题目描述

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

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

例 1：

输入: m = 3, n = 3, k = 5输出: 3解释: 乘法表:123246369第5小的数字是 3 (1, 2, 2, 3, 3).

例 2：

输入: m = 2, n = 3, k = 6输出: 6解释: 乘法表:123246第6小的数字是 6 (1, 2, 2, 3, 4, 6).

2.思路

2.1 代码

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

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      42      4  6      83   6  9      124      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 的数的个数，然后根据个数确定下一轮循环的范围

女性物流园