LeetCode.378.Kth Smallest Element in a Sorted Matrix 有序矩阵中第K小的元素

题目描述

378 Kth Smallest Element in a Sorted Matrix
https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/

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

示例：

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

返回 13。

提示：你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

---

相似题目

TopK问题
LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数
LeetCode.703.Kth Largest Element in a Stream 数据流中的第K大元素
LeetCode.378.Kth Smallest Element in a Sorted Matrix 有序矩阵中第K小的元素
LeetCode.347.Top K Frequent Elements 前K个高频元素
LeetCode.剑指offer.040.数组中最小的k个数
LeetCode.023.Merge k Sorted Lists 合并K个排序链表

归并排序问题
LeetCode.021.Merge Two Sorted Lists 合并两个有序链表
LeetCode.023.Merge k Sorted Lists 合并K个排序链表

---

解题过程

二分查找

有序矩阵中左上角元素是最小值 left，右下角是最大值 right，第 k 小的元素肯定在这个范围内，二分搜索。
每次选择中间值 mid，统计矩阵中小于等于 mid 的元素个数 lessCount
如果 lessCount < k，则说明 mid 值较小，第 k 小值肯定在 [mid + 1, right] 范围内
如果 lessCount >= k，说明 mid 值较大或 mid 值就是第 k 小值，在 [left, mid] 范围内继续搜索

由于矩阵是有序的，统计小于等于 target 的元素个数时间复杂度是 O(n)，二分的时间复杂度是 log(r-l)，总的时间复杂度是 nlogn(r-l)
空间复杂度 O(1)

private static class SolutionV202007 {
    public int kthSmallest(int[][] matrix, int k) {
        int left = matrix[0][0], right = matrix[matrix.length - 1][matrix[0].length - 1];
        while (left < right) {
            int mid = left + (right - left) / 2;
            int lessCount = countLess(matrix, mid); // 小于等于 mid 的元素个数
            if (lessCount < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    // 统计有序矩阵 matrix 中小于等于 target 的元素个数
    private int countLess(int[][] matrix, int target) {
        int count = 0;
        // 从左下角开始往右上角遍历
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] <= target) {
                // 小于等于 target，往右走，第 j 列上面的元素肯定也都比 target 小，所以 count 加 i + 1
                count += i + 1;
                j++;
            } else {
                // 大于 target，往上走
                i--;
            }
        }
        return count;
    }
}

堆/优先队列归并排序

使用最小堆维护每行的一维数组的最小值，每次取堆顶也就是 n 个最小值中的最小值，然后被取了最小值的数组用他的下一个元素补到堆中，一直到获得第 k 个元素。

---

GitHub代码

algorithms/leetcode/leetcode/_378_KthSmallestElementInSortedMatrix.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_378_KthSmallestElementInSortedMatrix.java

---