668. 乘法表中第k小的数

Difficulty

Hard

Tags

二分查找

URL

https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/

Star

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

思路

参考

378. 有序矩阵中第 K 小的元素，本题的矩阵虚拟的


class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        left, right = 1, m*n
        while left <= right:
            mid = left + (right - left) // 2
            temp = self.helper(m, n, mid)
            # print(left, right, mid, temp)
            if temp < k:
                left = mid + 1
            else:
                right = mid - 1

        return left

    def helper(self, m: int, n: int, mid: int) -> int:
        """统计这个 乘法表格中 小于等于 mid 的个数
        从右上角开始遍历
        """
        count = 0
        i, j = 1, n
        while i <= m and j >= 1:
            if i * j <= mid:
                count += j
                i += 1
            else:
                j -= 1
        return count