题目大意：
乘法表中第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).
注意：
m和n的范围在 [1, 30000] 之间。k的范围在 [1, m * n] 之间。
解题思路分析：
当看到这道题的取值范围之后，我们不难发现这个数量级是不可能采用动态规划或者递归加记忆数组方式的，暂且不论时间复杂度如何，单纯从记忆数组出发30000 * 30000的规模也会导致内存溢出。因此这种情况下我们应该首先想到二分查找这种logn级别的算法。
本题求解的是乘法表中第k小的数字，为了方便解释，我们定义该数字为N。换句话说，小于等于N的个数应该应该大于等于k个。这句话听起来有些绕口，进一步解释一下，如果集合中的数字在没有重复的情况下，一定只有k-1个数字小于N，进而小于等于N的个数就是k，因为N就是第k小的数字嘛！但是乘法表这个集合中是存在相同数字的，所以小于等于N的个数可能会多于k，多余出来的这部分实际上就是与N相同的数字个数。
但是无论如何，我们应该能够想象到，随着N的增加或者减小，N在乘法表集合中的大小排名也会相应的增加或者减小，这种线性关系正好对应了本题需要使用到的二分查找的思路。我们将左边界定义为1，右边界定义为m*n，然后取中值mid，查看mid在乘法表中的排名（方法稍后叙述），该排名如果大于等于k，mid值减一作为新的右边界，反之mid值加一作为新的左边界。最终left既是答案。这一段的叙述是标准的二分查找的解题思路，如果你对二分的边界问题不是很清楚，强烈建议参考一下我之前总结的文章： LEETCODE常见算法之二分查找超详细白话讲解 ，这里不再详述。
最后就是如何计算出某一数字在乘法表中的大小排名呢？乘法表是一个有规律的二维数组，第一行中的数字是1，2，3 … n, 第二行则是 2, 4, 6 … 2n, 第三行是3, 6, 9 … 3n。这样我们可以使用当前数字 N / 行数来计算出当前行中小于等于N的个数。这个很好理解，比如当前数字是8，那么第一行中小于等于8的数字就是8个（8 / 1 = 8）, 同理第二行中小于等于8的数字就是4个 (8 / 2 = 4)。不过这里有一个小坑需要注意下，每一行计算出来的这个个数是不能大于每一行的列数的，因此这里需要去一下最小值 min(列数，N / 当前行数)。
实现代码：
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 count = getCountLessThanNum(mid, m, n); // 小于等于当前数字的个数
if(count >= k) right = mid - 1;
else left = mid + 1;
}
return left;
}
// 计算出小于等于当前数字的个数
int getCountLessThanNum(int num, int m, int n) {
int count = 0;
for(int i=1;i<=n;i++){
count+=Math.min(num/i, m);
}
return count;
}
}本题解法执行时间为17ms。
Runtime: 17 ms, faster than 31.27% of Java online submissions for Kth Smallest Number in Multiplication Table.
Memory Usage: 35.6 MB, less than 94.37% of Java online submissions for Kth Smallest Number in Multiplication Table.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-668-kth-smallest-number-in-multiplication-table-解题思路分析/