题目描述
几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第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.6
1
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