leecode 378 有序矩阵中第k小的元素

雨点打透心脏的1/2处 2023-05-31 06:53 17阅读 0赞

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

示例:

matrix = \[  
\[ 1, 5, 9\],  
\[10, 11, 13\],  
\[12, 13, 15\]  
\],  
k = 8,

返回 13。

思路1个是，堆，这个很简单。  
思路2是二分查找，利用了有序，不过必须mid后必须查看元素个数。

class Solution {
        
        public int kthSmallest(int[][] matrix, int k) {
        
            
            // 行
            int r = matrix.length;
            // 列
            int c = matrix[0].length;
            int left = matrix[0][0];
            int right = matrix[r-1][c-1];
    
            while(left < right){
        
    
                int mid = left+(right- left)/2;
                int cunt = findNotBigger(matrix,mid,r,c);
                if(cunt < k)
                {
        
                    left = mid+1;
                }else{
        
                    right = mid;
                }
    
            }
            return right;
        }
        public int findNotBigger(int[][] matrix,int mid,int r,int c){
        
    
            int i = r-1;
            int j = 0;
            int count = 0;
            while(i>=0 && j<c){
        
                if(matrix[i][j]<=mid)
                {
        count+=i+1;
                j++;
    
            }else{
        
                i--;
            }
            }
            return count;
        }
    
    }