做网站架构,搜索引擎入口yandex,济南营销网站建设公司,网站产品介绍页面的布局方案文章目录1题目理解2 思路分析2.1二分思路2.2计算小于等于middle值的个数3 拓展解决leetcode 6681题目理解
输入#xff1a;一个nxn的矩阵#xff0c;每一行从左到右按照升序排列#xff0c;每一列从上到下按照升序排列。一个整数k。 输出#xff1a;这个矩阵中第k小的数。…
文章目录1题目理解2 思路分析2.1二分思路2.2计算小于等于middle值的个数3 拓展解决leetcode 6681题目理解
输入一个nxn的矩阵每一行从左到右按照升序排列每一列从上到下按照升序排列。一个整数k。 输出这个矩阵中第k小的数。 规则矩阵中数字可能重复输出结果应该排序后的第k个数。
例如 matrix [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k 8 结果13
2 思路分析
来源于力扣官方分析网址。 输入矩阵matrix每一行可以看做是一个排序好的数组可以将这几个小数组排序好之后取第k个数即可。排序几个已经排序好的数组可以参考leetcode23。时间复杂度O(klogn)。
因为同时每一列也是排序号的考虑用二分查找实现。
2.1二分思路
返回值一定在matrix[0][0]到matrix[n-1][n-1]之间。令函数g(x){matrix中小于等于x的数量}{#of(matrix[i][j]x)}。 g(x)是一个递增的函数x越大g(x)越大。 返回值是满足g(x)k的最小值。 套用模板。
class Solution {public int kthSmallest(int[][] matrix, int k) {int n matrix.length;int l matrix[0][0];int r matrix[n-1][n-1];while(lr){int middle l ((r-l)1);if(countSmallerOrEqual(matrix,middle,n)k){r middle - 1;}else{l middle 1;}}return l;}
}2.2计算小于等于middle值的个数
接下来的问题是如何数出middlemiddlemiddle的数量。 可以发现一个性质任取一个数 midmid 满足 l≤mid≤rl\leq mid \leq rl≤mid≤r那么矩阵中不大于 mid 的数肯定全部分布在矩阵的左上角。
例如下图取 mid8
从图中可以看到大于middle与小于等于middle的数被一条锯齿形状分成了2部分 。 我们可以从左下角开始遍历。 private int countSmallerOrEqual(int[][] matrix, int middle, int n){int i n - 1;int j 0;int num 0;while(i0 jn){if(matrix[i][j]middle){num i1;j;}else{i--;}}return num;}时间复杂度O(nlog(r−l))。二分查找进行次数为O(log(r−l))O(log(r-l))O(log(r−l))每次操作时间复杂度为 O(n)。
当然我们也可以每次遍历一个子数组二分查找个数。
private int countSmallerOrEqual(int[][] matrix, int middle, int n){int num 0;for(int i 0;in;i){int l 0, r n-1;while(lr){int m l ((r-l)1);if(matrix[i][m]middle){r m - 1;}else{l m 1;}}if(l0){num l;}} return num;}3 拓展解决leetcode 668
leetocde 668 Kth Smallest Number in Multiplication Table 与本题目非常类似。 每个人都知道乘法表。输入整数mn表示m行n列的乘法表。在这个乘法表中找到第k小元素。 例如 Input: m 3, n 3, k 5 Output: 3 Explanation: 乘法表是这样的: 1 2 3 2 4 6 3 6 9
The 5-th 小元素是 3 (1, 2, 2, 3, 3).
参考网址
这个乘法表与上面题目中的矩阵具有相同的性质每一行每一列都是有序的。同样也是要查找第k小元素同样矩阵中是有重复元素的。把上面代码框架抄写一下。
class Solution {public int findKthNumber(int m, int n, int k) {int l 1;int r m*n;while(lr){int middle l ((r-l)1);if(countSmallerOrEqual(m,n,middle)k){r middle - 1;}else{l middle 1;}}return l;}}不同的地方是上提的矩阵是确定的已经生成好的而本题需要自己生成矩阵。 题目要求m n 的范围是[1, 30000]如果生成矩阵可能会引起内存不足。 当我们要计算有多少个数小于等于middle的时候是不是可以不生成矩阵呢 例如 m3n3middle5查找这个矩阵中有多少个值小于等于5。 对于第3行是从1到3依次乘以35/31有1个元素小于等于5。 对于第2行是从1到3依次乘以25/22有2个元素小于等于5。 对于第1行是从1到3依次乘以15/15但是n3 所以有3个元素小于等于5。 总小于等于5元素个数是1236。由此可以看出不需要生成矩阵也可以计算。 private int countSmallerOrEqual(int m,int n,int middle){int num 0;for(int i1;im;i){num Math.min(middle/i,n);}return num;}
