0668：乘法表中第k小的数（★★）

Ian

2016-10-29 约 350 字预计阅读 1 分钟次阅读

力扣第 668 题

题目

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

乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j（下标从 1 开始）。

给你三个整数 m、n 和 k，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字。

示例 1：

输入：m = 3, n = 3, k = 5
输出：3
解释：第 5 小的数字是 3 。

示例 2：

输入：m = 2, n = 3, k = 6
输出：6
解释：第 6 小的数字是 6 。

提示：

1 <= m, n <= 3 * 10⁴
1 <= k <= m * n

相似问题：

分析

典型的二分问题，对于数字 x，计算表中 <=x 的个数即可。

解答

1
2
3
4
5


class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def cal(x):
            return sum(min(x//i,n) for i in range(1,m+1))
        return bisect_left(range(m*n),k,key=cal)

606 ms

目录

0668：乘法表中第k小的数（★★）

题目

分析

解答