[LeetCode]668. 乘法表中第k小的数(Kth Smallest Number in Multiplication Table)

题目描述

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

注意:

  1. m 和 n 的范围在 [1, 30000] 之间。
  2. k 的范围在 [1, m * n] 之间。

解题思路

二分法。因为矩阵是有序的,可对 1m*n 之间的数字进行二分,每次统计矩阵中小于等于 mid 的数字的个数 count,根据 countk 来缩小二分的范围。
统计 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
13
class 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

参考

https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table/solution/er-fen-cha-zhao-si-lu-xiang-jie-python3-by-cowry/