378. 有序矩阵中第 K 小的元素

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

给你一个 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;
    }
}