notepad做网站技巧,硬件工程师需要学哪些,网站建设如何选择域名,优化网站排名推荐公司力扣链接#xff1a;题目 参考地址#xff1a;参考
思路#xff1a;二分查找 把矩阵想象成一维的已排好序的数组#xff0c;用二分法找第k小的数字。 假设m行n列#xff0c;则对应一维下标范围是从1到mn#xff0c;初始#xff1a; l1; rmn; mid(lr)/2 设mid在第i行题目 参考地址参考
思路二分查找 把矩阵想象成一维的已排好序的数组用二分法找第k小的数字。 假设m行n列则对应一维下标范围是从1到mn初始 l1; rmn; mid(lr)/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, 初始count0; 即count 0~i-1行的值的数量 , 即mid/列数 * 列数mid/列数得到mid所在行号 2此外下面的ki~m-1行也存在比matrix[i][j]小/等于的数第k行mid/k列左边的值必然比matrix[i][j]小 ——因为matrix[i][j]i * j, jmid/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, ki~m-1 3综上mid对应的矩阵值的数量为 // 当前行之上的行肯定比mid所指值小统计比mid所指值小的个数count mid/n * n; // 行数*每行有多少个// 当前行及之下的行也有比mid所指值小的值也要统计for(int imid/n1; im; i){ // mid/n1是当前行// 当前行有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 l1, rm*n;// m行n列当前行idxmid/nmid%n矩阵nums[][]while(lr){int mid (lr)/2;int count 0;// 当前行之上的行肯定比mid所指值小统计比mid所指值小的个数count mid/n * n; // 行数*每行有多少个// 当前行及之下的行也有比mid所指值小的值也要统计for(int imid/n1; im; i){ // mid/n1是当前行// 当前行有mid/i个数比mid对应的值小count mid/i;}if(countk){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
