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 。

二分查找

由题目给出的性质可知, 矩阵内的元素左上角最小, 右下角最大. 假设left和right分别为二分法使用时的最大最小值. 使用二分法的步骤是

  1. 计算出矩阵内最大值和最小值的均值(即mid=(left+right)/2)

  2. 然后从矩阵的左下角(matrix[n-1][0])到右上角(matrix[0][n-1])进行遍历, 找出小于等于mid的元素的个数.

    如图所示, 如果当前元素matrix[i][j]小于等于mid, 则小于等于mid的元素共有i+1个(考虑到数组下标从0开始), 并且向右移动. 否则向上移动. 直至最后走出矩阵.

  3. 计算出来小于等于mid的元素数目大于k, 说明二分算法需要在右边继续. 否则二分算法在左边继续.

代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0], right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = (left + right) / 2;
            if (lessEqualThanMid(matrix, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int lessEqualThanMid(int[][] matrix, int mid) {
        int n = matrix.length;
        int i = n - 1, j = 0, sum = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                sum += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return sum;
    }
}