【笔记】【矩阵的二分】668. 乘法表中第k小的数

力扣链接：题目
参考地址：参考

思路：二分查找
把矩阵想象成一维的已排好序的数组，用二分法找第k小的数字。

假设m行n列，则对应一维下标范围是从1到mn，初始：
l=1; r=mn; mid=(l+r)/2
设mid在第i行，第j列，即mid对应的值为matrix[i][j]，
注意：由于乘法表中的元素并不是线性排序的，所以不能直接用mid和k比较，这样找不出第k小具体在矩阵的哪个位置，mid并不一定在矩阵中心，所以需要每次统计mid位置实际在矩阵中有多少比他小的数。

（1）由矩阵可知，0~i-1行必然比matrix[i][j]小，假设mid是matrix[1][1]，比它小的值的数量为count, 初始count=0;
即，count += 0~i-1行的值的数量 , 即mid/列数 * 列数，mid/列数得到mid所在行号

（2）此外，下面的k=i~m-1行也存在比matrix[i][j]小/等于的数：第k行（mid/k）列左边的值必然比matrix[i][j]小
——因为matrix[i][j]=i * j, j=mid/i, matrix[k][mid/k] = matrix[i][mid/i] = matrix[i][j]，
而左边列数<mid/k, 所以（左边的值=k*左边列数） < （matrix[k][mid/k]=k * mid/k）= matrix[i][j]
即，count += mid/k, k=i~m-1

（3）综上，<=mid对应的矩阵值的数量为：

	// 当前行之上的行肯定比mid所指值小，统计比mid所指值小的个数count += mid/n * n;   // 行数*每行有多少个// 当前行及之下的行也有比mid所指值小的值，也要统计for(int i=mid/n+1; i<=m; i++){  // mid/n+1是当前行// 当前行有mid/i个数比mid对应的值小count += mid/i;}

或者：

	for (int i = 1; i <= m; i++) {count += Math.min(x / i, n);}

总体代码如下：

class Solution {public int findKthNumber(int m, int n, int k) {int l=1, r=m*n;// m行n列，当前行idx：mid/n+mid%n，矩阵nums[][]while(l<=r){int mid = (l+r)/2;int count = 0;// 当前行之上的行肯定比mid所指值小，统计比mid所指值小的个数count += mid/n * n;   // 行数*每行有多少个// 当前行及之下的行也有比mid所指值小的值，也要统计for(int i=mid/n+1; i<=m; i++){  // mid/n+1是当前行// 当前行有mid/i个数比mid对应的值小count += mid/i;}if(count<k){l = mid + 1;}else{r = mid - 1;}}return l;}
}

二分法为什么输出的数一定在乘法表里?
https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/solutions/891712/guan-fang-ti-jie-yu-zi-ji-de-yi-wen-java-nxu8