1. 题目描述
几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？
给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 示例
例 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] 之间。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
3. 思路
这里求第k小的数字，我考虑的是，从1…n,求每个数的因数个数，然后就可以求出1在表中占的数量，将每个数的因数值统计起来，当相加超过k时,则表示该n为所求值。
4. 遇上的问题
时间复杂度太高了。导致算不出来
5. 具体实现代码
自己写的代码
func findKthNumber(m int, n int, k int) int {
targetNum := 0
for j:=1;j<=m*n;j++{
factorCount := 0
for i:=1;i*i<=j;i++{
if j % i == 0{
if i <= m && j / i <= n{
factorCount++
}
if i <= n && j / i <= m && j / i != i{
factorCount++
}
}
}
targetNum = targetNum + factorCount
if targetNum>=k{
return j
}
}
return 0
}
6. 官方题解
func findKthNumber(m, n, k int) int {
return sort.Search(m*n, func(x int) bool {
count := x / n * n
for i := x / n + 1; i <= m; i++ {
count += x / i
}
return count >= k
})
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/solution/cheng-fa-biao-zhong-di-kxiao-de-shu-by-l-521a/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
根据官方题解思路写的Go二分查找
func findKthNumber(m int, n int, k int) int {
left := 1
right := m*n
mid := (left+right)/2
for left<right {
factorCount := 0
for j := 1; j <= m;j++{
if mid/j == 0 {
break
}
thisRowCount := mid/j
if thisRowCount > n {
thisRowCount = n
}
factorCount = factorCount + thisRowCount
}
if factorCount >= k {
right = mid //不用mid-1是因为mid也有可能是目标值
}else {
left = mid+1 //+1是因为left和比left小的值都不可能是目标值
}
mid = left + (right-left)/2
}
return mid
}
注意事项1：
乘法表内每行都是x的倍数。
比如说:
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| 2 | 4 | 6 | 8 |
| 3 | 6 | 9 | 12 |
| 4 | 8 | 12 | 16 |
在第二行中，数字都是2的倍数。
当求比4小或者等于4的数的时，
- 第一行：4/1 = 4
- 第二行：4/2 =2
- 第三行：4/3 =1
- 第四行：4/4 =1
所以表中比4小的数有4+2+1+1=10个
如果这个时候题目求第9小的数，那么我们就可以返回4。
注意事项2：
二分法的中位数mid用于求乘法表内有多少个数counts比mid小,再把counts和目标值作比较 k，
如果counts<k,则中位数mid太小了，左边界值left右移，即left=mid+1。
如果counts>=k,则中位数mid可能大了或者刚刚好，右边界值right左移，即right=mid。
注意事项3：
由于m,n两值大小不确定，所以当计算每一行有多少个值小于等于的个数counts时，如果counts大于n,则取n
7 题目来源
困难题暴力法不可行，学习了一个乘法表行即倍数的概念，又复习了一遍二分法。------swrici
