By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、有序矩阵中第K小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

请注意，它是排序后的第 k 小元素

示例：

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

返回 13。

1.1、解题思路

其中每行和每列元素均按升序排序 ,所以最小值在左上交，最大值在右上角

image-20200702110514066

image-20200702110620771

image-20200702110630284

1.2、算法

public int kthSmallest(int[][] matrix, int k) {
    //其中每行和每列元素均按升序排序 ,所以最小值在左上交，最大值在右上角
    int left = matrix[0][0];
    int right = matrix[matrix.length - 1][matrix.length - 1];
    while (left < right) {
        int mid =   ((right + left) / 2);
        //计算小于等于中位数的个数有多少个
        int count = moreThanMid(mid, matrix);
        if (count < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}



public int moreThanMid(int mid, int[][] matrix) {
    int i = matrix.length -1 ;
    int j = 0;
    int count = 0;
    while (i >= 0 && j < matrix.length) {
        if (matrix[i][j] <= mid) {
            // i + 1 为当前满足if的列上个数
            count += i + 1;
            j++;
        } else {
            i--;
        }
    }
    return count;
}

1.3、测试

  @Test
    public void test() {

        int[][] matrix = {
                {1, 5, 9},
                {10, 11, 13},
                {12, 13, 15}
        };

        System.out.println(kthSmallest(matrix, 8));
    }

​

ContactAuthor