378. The Kth Smallest Element in an Ordered Matrix

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

---

前言

给你一个 n x n 矩阵 matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素.
请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素.

你必须找到一个内存复杂度优于 O(n2) 的解决方案.

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix
著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处.

解题思路

给定一个目标,想知道<= 100的数有几个,How fast can seek out?

往左走,获得0个

走到90,左边的都是小于100的数,Get the number on the left

往下走,小于等于100的,Add the number on the left,
So had been stuck to the end,How many did you get the correct array number<=100

二分

Who is the youngest of the entire array?左上角的数
The whole array,Who is the largest number?右下角的数
One hundred small number must be in one to1000之间, 看看<= 500的数有几个?

如果<=500有200个,目标大了

May finally get<=785的数有100个,But don't have the number in the array,应该是< =785And the nearest number
Every time I let you ask two information,
第一,Several number less than or equal to a certain value,
第二,最接近它的是谁?

代码

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;
    }
}