LeetCode 668. Kth Smallest Number in Multiplication Table 2019-08-20

题目描述

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

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

tag

二分 矩阵题

样例

1
2
3
4
5
6
7
8
9
输入: m = 3, n = 3, k = 5
输出: 3
解释:
乘法表:
1 2 3
2 4 6
3 6 9

第5小的数字是 3 (1, 2, 2, 3, 3).

算法1

(二分) O(logn)
思路
复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:

def _check(mid, m, n, k):
count = 0
for i in range(1, m + 1):
count += min(mid // i, n)
return count >= k

left = 1
right = m * n + 1

while left < right:

mid = (left + right) // 2

if _check(mid, m, n, k):
right = mid
else:
left = mid + 1

return left