( 数组和矩阵) 378. 有序矩阵中第 K 小的元素 ——【Leetcode每日一题】-Toy模板网

这篇具有很好参考价值的文章主要介绍了( 数组和矩阵) 378. 有序矩阵中第 K 小的元素 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

难度：中等

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

你必须找到一个内存复杂度优于 $O(n^2)$ 的解决方案。

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：

输入：matrix = [[-5]], k = 1
输出：-5

提示：

n == matrix.length
n == matrix[i].length
1 <= n <= 300
$10^9 <= matrix[i][j] <= 10^9$
题目数据保证 matrix 中的所有行和列都按非递减顺序排列
$1 <= k <= n^2$

进阶：

你能否用一个恒定的内存(即 $O (1)$ 内存复杂度)来解决这个问题?
你能在 $O (n)$ 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。

💡思路：

法一：二分查找

找出二维矩阵中最小的数 l，最大的数 h，我们取中位数 mid = (l ＋ h) / 2，在二维矩阵中寻找小于等于 mid 的元素个数cnt：

若这个cnt 小于k，表明第k小的数在右半部分且不包含mid，即 l = mid + 1，h不变；
若这个cnt 大于等于k，表明第k小的数在左半部分且可能包含 mid，即 l 不变, h = mid - 1;
当l > h 时，第 k 小的数即被找出，等于l。

法二：归并排序

由题目给出的性质可知，这个矩阵的每一行均为一个有序数组。问题即转化为从这 n 个有序数组中找第 k 大的数，可以想到利用归并排序的做法，归并到第 k 个数即可停止。

一般归并排序是两个数组归并，而本题是 n 个数组归并，所以需要用小根堆维护，以优化时间复杂度。

🍁代码：(Java、C++)

法一：二分查找
Java

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int l = matrix[0][0], h = matrix[n - 1][n - 1];
        while(l <= h){
            int mid = l + (h - l) / 2;
            int cnt = 0;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n && matrix[i][j] <= mid; j++){
                    cnt++;
                }
            }
            if(cnt < k) l = mid + 1;
            else h = mid - 1;
        }
        return l;
    }
}

C++

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int l = matrix[0][0], h = matrix[n - 1][n - 1];
        while(l <= h){
            int mid = l + (h - l) / 2;
            int cnt = 0;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n && matrix[i][j] <= mid; j++){
                    cnt++;
                }
            }
            if(cnt < k) l = mid + 1;
            else h = mid - 1;
        }
        return l;
    }
};

法二：归并排序
Java

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        });
        int n = matrix.length;
        for(int i = 0; i < n; i++){//第一列分别为n数组的头结点
            pq.offer(new int[] {matrix[i][0], i, 0});
        }
        for(int i = 0; i < k - 1; i++){
            int[] now = pq.poll();//弹出最小的那个
            if(now[2] != n - 1){//不是一行的最后一个元素
                pq.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
            }
        }
        return pq.poll()[0];
    }
}

C++

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        struct point{
            int val, x, y;
            point(int val, int x, int y): val(val), x(x), y(y){};
            bool operator> (const point& a)const{
                return this->val > a.val;
            }
        };
        priority_queue<point, vector<point>, greater<point>> que;
        int n = matrix.size();
        for(int i = 0; i < n; i++){
            que.emplace(matrix[i][0], i, 0);
        }
        for(int i = 0; i < k - 1; i++){
            point now = que.top();
            que.pop();
            if(now.y != n - 1){
                que.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
            }
        }
        return que.top().val;
    }
};

🚀 运行结果：

( 数组和矩阵) 378. 有序矩阵中第 K 小的元素 ——【Leetcode每日一题】,LeetCode,leetcode,矩阵,算法

🕔 复杂度分析：

时间复杂度： $O (n l o g (r - l))$ ，二分查找进行次数为 $O (n l o g (r - l))$ , 每次操作时间复杂度为 $O (n)$ 。归并排序时间复杂度为 $O (k l o g n)$ ，归并 k 次，每次堆中插入和弹出的操作时间复杂度均为 $l o g n$ 。
空间复杂度： $O (1)$ ；归并排序空间复杂度为 $O (n)$ ，堆的大小始终为 n。