提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
@TOC
前言
给你一个 n x n 矩阵 matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。
你必须找到一个内存复杂度优于 O(n2) 的解决方案。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
给定一个目标,想知道<= 100的数有几个,怎么快能求出来?
往左走,获得0个
走到90,左边的都是小于100的数,获得左边的数量
往下走,小于等于100的,加左边的数,
就这样一直卡到结束,你正确的获得整个数组中有多少个数<=100
二分
整个数组中最小的是谁?左上角的数
那整个数组中,最大的数是谁?右下角的数
第一百小的数一定在一到1000之间, 看看<= 500的数有几个?
如果<=500有200个,目标大了
有可能最后得到<=785的数有100个,但是数组中没有这个数,应该是< =785并离它最近的数
我每次让你过的时候求俩信息,
第一,小于等于某一个值个数有几个,
第二,最接近它的是谁?
代码
class Solution {
public static class Info{
public int near;
public int num;
public Info(int n1,int n2){
near=n1;
num=n2;
}
}
public Info noMoreNum(int[][] matrix,int value){
int near=Integer.MIN_VALUE;
int num=0;
int n=matrix.length;
int m=matrix[0].length;
int row=0;
int col=m-1;
while(row<n&&col>=0){
if(matrix[row][col]<=value){
near=Math.max(near,matrix[row][col]);
num+=col+1;
row++;
}else{
col--;
}
}
return new Info(near,num);
}
public int kthSmallest(int[][] matrix, int k) {
int n=matrix.length;
int m=matrix[0].length;
int left=matrix[0][0];
int right=matrix[n-1][m-1];
int ans=0;
while(left<=right){
int mid=left+((right-left)>>1);
Info info=noMoreNum(matrix,mid);
if(info.num<k){
left=mid+1;
}else{
ans=info.near;
right=mid-1;
}
}
return ans;
}
}