当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.378.Kth Smallest Element in a Sorted Matrix 有序矩阵中第K小的元素

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


上一篇 LeetCode.032.Longest Valid Parentheses 最长有效括号

下一篇 LeetCode.剑指offer.009.用两个栈实现队列

阅读
评论
701
阅读预计3分钟
创建日期 2020-07-02
修改日期 2020-07-02
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论