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

题目描述

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

示例:

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

返回 13。

说明:

你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

思路

思路1：二分法

使用两个哨兵分别记录最大值和最小值（可以取到第k个值的区间），然后计算中间值的大小，根据这个中间值计算第k个值在二分区间中的位置，或者是大于多少个矩阵中的值，若比k大则属于前半区间，若小于等于k则处于后半区间，等于由于可能中间值不是矩阵中的值所以不能直接返回

代码

代码1

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            throw new RuntimeException("matrix is empty!");
        }
        int rowSize = matrix.length;
        int colSize = matrix[0].length;
        if (k > colSize * rowSize){
            throw new RuntimeException("matrix is less than k!");
        }
        
        int left = matrix[0][0];
        int right = matrix[matrix.length - 1][matrix[0].length - 1];
        int count = -1;
        
        while (left < right){
            int mid = (left + right) / 2;
            count = getCount(matrix, mid, rowSize, colSize);
            if (count < k){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return right;
    }
    
    private int getCount(int[][] matrix,int mid,int rowSize,int colSize){
        int rowIndex = rowSize - 1;
        int colIndex = 0;
        int count = 0;
        
        while (rowIndex >= 0 && colIndex < colSize){
            if (matrix[rowIndex][colIndex] <= mid){
                count += rowIndex + 1;
                colIndex ++;
            }else{
                rowIndex --;
            }
        }
        return count;
    }
}