题目

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

思路

首先

：涉及元素极多做不到遍历的二维矩阵里的第K小都可以用二分猜答案的套路，转化为“给定一个数，求矩阵中有多少个数比这个数小”，进而实现二分查找


本题题解：

1. 与常见二分不同点在于：本题二分是把值来当作边界，而不是下标作为边界
2. 获得在 m * n 乘法表中，找出每行有多少个值小于等于num， 其中每行的值为 i * j （i代表当前行，j代表当前列），通过 num // i 来获取每行小于等于 num 值的总个数
3. 乘法表 m * n 最小是1，最大是m * n, 通过提前判断加速算法
4. 由于目标值可能存在重复边界情况，需要注意不同条件的等号判定

题解

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        if k == 1:
            return 1
        if k == m * n:
            return m * n
        left, right = 1, m * n
        # 二分法求值
        while left < right:
            mid = left + ((right - left) >> 2)
            if self.countsum(m, n, mid) >= k:
                right = mid
            else:
                left = mid + 1
        return left

	# 求不超过mid的值的个数
    def countsum(self, m, n, mid):
        return sum(min(mid // i, n) for i in range(1, m + 1))