668.乘法表中第k小的数
668.乘法表中第k小的数
题解
题目：给定一张n * m的乘法表，问从小到大第k个数是多少
思路：二分答案，将题目转换为小于等于x的数有几个，二分出小于等于x的数有k个时，x就是答案
- 那么现在的问题就是求小于等于x的数有几个，然后不断二分x
- 如何求小于等于x的数呢？
以x=4为例，第一行有min(4/1,n)个，第二行有min(4/2,n)个…以此类推
- 在乘法表中每一行都是上一行的2倍
- x 整除以 i 得到了 x 是 i 的多少倍，表示在第 i 行有多少数字小于等于 x
- 现在得到了小于等于 x的数量，从1~n*m二分答案即可
代码
func findKthNumber(m int, n int, k int) int { return sort.Search(m*n, func(x int) bool { count := 0 for i := 1; i <= m; i++ { count += min(x/i, n) } return count >= k }) } func min(i, j int) int { if i > j { return j } return i }
