题目描述
几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第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] 之间。
解题思路
二分法。因为矩阵是有序的，可对 1 到 m*n 之间的数字进行二分，每次统计矩阵中小于等于 mid 的数字的个数 count，根据 count 与 k 来缩小二分的范围。
统计 count 时，考虑到第 i 行的形式为 [1*i, 2*i, 3*i, ..., k*i, ..., n*i]，所以该行小于等于 mid 的数字有 min(mid // i, n) 个。
代码
Python 3.61
2
3
4
5
6
7
8
9
10
11
12
13class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
left, right = 1, m * n
while left < right:
mid = (left + right) >> 1
count = 0
for i in range(1, m + 1):
count += min(mid // i, n)
if count < k:
left = mid + 1
else:
right = mid
return left
执行用时 : 988 ms内存消耗 : 13.8 MB