难度: Hard
几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第 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 * 1041 <= k <= m * n运行时间: 174 ms
内存: 16.1 MB
class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
left, right = 1, m * n
while left < right:
p = left + (right - left) // 2
count = (p // n) * n
for i in range((p // n) + 1, m + 1):
count += p // i
if count >= k:
right = p
else:
left = p + 1
return left
这个题解使用了二分查找的思路。我们可以在 1 到 m*n 的范围内进行二分查找，每次根据当前数 p 在乘法表中小于等于 p 的数的个数 count，来判断第 k 小的数是在 p 的左边还是右边。如果 count >= k，说明第 k 小的数在 p 的左边，我们缩小右边界；否则第 k 小的数在 p 的右边，我们增大左边界。最终左右边界会收敛到第 k 小的数。
时间复杂度: O(m * log(m*n))
空间复杂度: O(1)
class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
left, right = 1, m * n
while left < right:
p = left + (right - left) // 2
# 计算乘法表中小于等于 p 的数的个数
count = (p // n) * n
for i in range((p // n) + 1, m + 1):
count += p // i
# 如果 count >= k，说明第 k 小的数在 p 的左边
if count >= k:
right = p
# 否则第 k 小的数在 p 的右边
else:
left = p + 1
return left
选择`left + (right - left) // 2`作为中点是为了防止在计算`(left + right) // 2`时发生整数溢出。当`left`和`right`都非常大的时候，直接相加可能导致超出整型变量的存储范围。而`left + (right - left) // 2`的方式先求差值再除以2，有效避免了这个问题，保证了计算的安全性。
计算`(p // n) * n`是基于乘法表的行的特性来估算某些行完全小于等于`p`的元素数量。对于每一行`i`，该行元素为`i, 2i, ..., ni`，故当`i <= p // n`时，第`i`行的所有`n`个元素都小于等于`p`。因此，对于所有`i <= p // n`的行，可以直接计算出这些行的元素数量总和为`(p // n) * n`。这种计算方式适用于初步估计，但不适用于所有情况，因为对于`i > p // n`的情况需要额外计算每行小于等于`p`的元素数。
从`(p // n) + 1`到`m + 1`进行迭代是因为对于`i <= p // n`的行，我们已经知道这些行的所有元素都小于等于`p`，所以这部分已经被初步计算为`(p // n) * n`。对于`i > p // n`，这些行中的元素不一定全部小于等于`p`，需要具体计算每行有多少元素小于等于`p`。因此，循环从`(p // n) + 1`开始，是为了计算那些不符合全部小于等于`p`的行的具体符合条件的元素数量。
如果`count >= k`则将`right`设置为`p`是基于二分查找的策略，即在可能的数值范围内寻找第`k`小的数。这种方式不会使得最终结果偏小，因为这只是将查找范围缩小到包含第`k`小数的更小区间。每次迭代都是基于`count`与`k`的比较来调整`left`或`right`，确保最终`left`和`right`收敛到同一个值，那就是第`k`小的数。通过持续缩小范围，最终当`left == right`时，这个共同值就是正确的第`k`小的数。