给出n,m,k,输出在n*m的乘法表中第k小的数。
时间: 2023-06-19 14:05:21 浏览: 83
可以使用二分查找来解决这个问题。
首先,我们可以观察到乘法表中的任何一个数都可以用 i * j 的形式表示,其中 i 和 j 分别是乘法表中的两个数。那么,我们可以将这个问题转化为寻找第 k 小的数,使得 i 和 j 分别不大于 n 和 m。
接下来,我们可以使用二分查找来尝试寻找这个数。具体来说,我们可以二分查找可能的答案 x,然后在乘法表中寻找小于等于 x 的数的个数 count。如果 count 小于 k,那么我们就需要将二分查找的左边界向右移动,否则我们就需要将右边界向左移动。
最后,当左右边界相等时,它们所代表的数就是我们要寻找的第 k 小的数。
下面是具体的代码实现:
```python
def count_less_or_equal(mid, n, m):
"""
计算乘法表中小于等于 mid 的数的个数
"""
count = 0
for i in range(1, n+1):
count += min(mid // i, m)
return count
def find_kth_number(n, m, k):
"""
在 n*m 的乘法表中寻找第 k 小的数
"""
left, right = 1, n * m
while left < right:
mid = (left + right) // 2
if count_less_or_equal(mid, n, m) < k:
left = mid + 1
else:
right = mid
return left
```
时间复杂度为 O(log(nm) * (n + m))。