2021-8-18 378. 有序矩阵中第 K 小的元素（堆排序（归并排序），二分法）

本文主要是介绍2021-8-18 378. 有序矩阵中第 K 小的元素（堆排序（归并排序），二分法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注：

题目：

题给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

示例 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
-109 <= matrix[i][j] <= 109
题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
1 <= k <= n2

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

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

具体如何归并，可以参考力扣 23. 合并K个排序链表。

复杂度分析
时间复杂度：O(klogn)，归并 k 次，每次堆中插入和弹出的操作时间复杂度均为 logn。
空间复杂度：O(n)，堆的大小始终为 n。

class Solution {
public:int kthSmallest(vector<vector<int>>& matrix, int k) {class point{public:int val,x,y;point(int val_,int x_,int y_):val(val_),x(x_),y(y_){};};class compare{public:bool operator() (const point &a,const point &b) {return a.val>b.val;}};priority_queue<point,vector<point>,compare> points;int row=matrix.size();int col=matrix[0].size();for(int i=0;i<row;i++){points.emplace(matrix[i][0],i,0);}for(int i=0;i<k-1;i++){point t=points.top();points.pop();if(t.y+1==col){continue;}points.emplace(matrix[t.x][t.y+1],t.x,t.y+1);}return points.top().val;}
};

方法二 二分查找
思路及算法

由题目给出的性质可知，这个矩阵内的元素是从左上到右下递增的（假设矩阵左上角为matrix[0][0]）。以下图为例：

我们知道整个二维数组中 matrix[0][0] 为最小值，matrix[n−1][n−1] 为最大值，现在我们将其分别记作 l 和 r。

可以发现一个性质：任取一个数 mid 满足 l≤mid≤r，那么矩阵中不大于 mid 的数，肯定全部分布在矩阵的左上角。

例如下图，取 mid=8：

我们可以看到，矩阵中大于 mid 的数就和不大于 mid 的数分别形成了两个板块，沿着一条锯齿线将这个矩形分开。其中左上角板块的大小即为矩阵中不大于 mid 的数的数量。

读者也可以自己取一些 mid 值，通过画图以加深理解。

我们只要沿着这条锯齿线走一遍即可计算出这两个板块的大小，也自然就统计出了这个矩阵中不大于 mid 的数的个数了。

走法演示如下，依然取 mid=8：

可以这样描述走法：

1. 初始位置在 matrix[n - 1][0]（即左下角）；
2. 设当前位置为 matrix[i][j]。若 matrix[i][j]≤mid，则将当前所在列的不大于 midmid 的数的数量（即i+1）累加到答案中，并向右移动，否则向上移动；
3. 不断移动直到走出格子为止。

我们发现这样的走法时间复杂度为 O(n)，即我们可以线性计算对于任意一个 mid，矩阵中有多少数不大于它。这满足了二分查找的性质。

不妨假设答案为 x，那么可以知道l≤x≤r，这样就确定了二分查找的上下界。

每次对于「猜测」的答案 mid，计算矩阵中有多少数不大于 mid ：

1. 如果数量不少于 k，那么说明最终答案 x 不大于 mid；
2. 如果数量少于 k，那么说明最终答案 x 大于 mid。

这样我们就可以计算出最终的结果 x 了。

复杂度分析
时间复杂度：O(nlog(r−l))，二分查找进行次数为O(log(r−l))，每次操作时间复杂度为O(n)。
空间复杂度：O(1)。

class Solution {
public:bool check(vector<vector<int>> matrix,int mid,int k){int i=matrix.size()-1;int j=0;int count=0;while(i>=0&&j<matrix[0].size()){if(matrix[i][j]<=mid){j++;count+=(i+1);}else{i--;}}return k<=count;}int kthSmallest(vector<vector<int>>& matrix, int k) {int left=matrix[0][0];int right=matrix[matrix.size()-1][matrix.size()-1];while(left<right){int mid=left+(right-left)/2;if(check(matrix,mid,k)==true){right=mid;}else{left=mid+1;}}return left;}
};

这篇关于2021-8-18 378. 有序矩阵中第 K 小的元素（堆排序（归并排序），二分法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---