?378. 有序矩陣中第 K 小的元素

難度：中等

給你一個 $nxn$ 矩陣 $matrix$ ，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。
請注意，它是 排序后 的第 k 小元素，而不是第 k 個 不同 的元素。

你必須找到一個內(nèi)存復(fù)雜度優(yōu)于 $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$
• 題目數(shù)據(jù) 保證 matrix 中的所有行和列都按 非遞減順序 排列
• $1<=k<=n^2$

進(jìn)階：

• 你能否用一個恒定的內(nèi)存(即 $O(1)$ 內(nèi)存復(fù)雜度)來解決這個問題?
• 你能在 $O(n)$ 的時間復(fù)雜度下解決這個問題嗎?這個方法對于面試來說可能太超前了，但是你會發(fā)現(xiàn)閱讀這篇文章（ this paper ）很有趣。

??思路：

法一：二分查找

找出二維矩陣中最小的數(shù) l，最大的數(shù) h，我們?nèi)?strong>中位數(shù) mid = (l ＋ h) / 2，在二維矩陣中尋找小于等于 mid 的元素個數(shù)cnt：

• 若這個cnt 小于k，表明第k小的數(shù)在右半部分且不包含mid，即 l = mid + 1，h不變；
• 若這個cnt 大于等于k，表明第k小的數(shù)在左半部分且可能包含 mid，即 l 不變, h = mid - 1;
• 當(dāng)l > h 時，第 k 小的數(shù)即被找出，等于l。

法二：歸并排序

由題目給出的性質(zhì)可知，這個矩陣的每一行均為一個有序數(shù)組。問題即轉(zhuǎn)化為從這 n 個有序數(shù)組中找第 k 大的數(shù)，可以想到利用歸并排序的做法，歸并到第 k 個數(shù)即可停止。

一般歸并排序是兩個數(shù)組歸并，而本題是 n 個數(shù)組歸并，所以需要用小根堆維護(hù)，以優(yōu)化時間復(fù)雜度。

??代碼：(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數(shù)組的頭結(jié)點
            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;
    }
};

?? 運行結(jié)果：

?? 復(fù)雜度分析：

• 時間復(fù)雜度：$O(nlog(r?l))$，二分查找進(jìn)行次數(shù)為 $O(nlog(r?l))$, 每次操作時間復(fù)雜度為$O(n)$。歸并排序時間復(fù)雜度為$O(klogn)$，歸并 k 次，每次堆中插入和彈出的操作時間復(fù)雜度均為$logn$。
• 空間復(fù)雜度：$O(1)$；歸并排序空間復(fù)雜度為$O(n)$，堆的大小始終為 n。

題目來源：力扣。

放棄一件事很容易，每天能堅持一件事一定很酷，一起每日一題吧！
關(guān)注我 leetCode專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-626853.html

注： 如有不足，歡迎指正！

到了這里，關(guān)于( 數(shù)組和矩陣) 378. 有序矩陣中第 K 小的元素 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！