Leetcode 378. Kth Smallest Element in a Sorted Matrix

378. Kth Smallest Element in a Sorted Matrix

Total Accepted: 3183
Total Submissions: 7968
Difficulty: Medium

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

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

return 13.
Note:

思路：

方法一：向量的每行每列都是升序排序的，利用这个排序条件，维护一个优先队列，放置每列当前的最小数，然后只要弹出k-1个数，第k个数就是答案。

方法二：简单粗暴，直接对所有元素升序排序后，取第k个元素。

代码：

方法一：

priority_queue关于pair的比较函数不太会写。

 1 class Solution {
 2 public:
 3     int kthSmallest(vector<vector<int> >& matrix, int k) {
 4         priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > colmin;
 5         int bound=k<matrix.size()?k:matrix.size();
 6         int n=matrix.size();
 7         for(int i=0;i<bound;i++) colmin.push(make_pair(matrix[0][i],i));
 8         for(;k>1;k--){
 9             int i=colmin.top().second/n;
10             int j=colmin.top().second%n;
11             colmin.pop();
12             if(i==n-1) continue;
13             colmin.push(make_pair(matrix[i+1][j],(i+1)*n+j));
14         }
15         return colmin.top().first;
16     }
17 };

方法二：

 1 class Solution {
 2 public:
 3     int kthSmallest(vector<vector<int> >& matrix, int k) {
 4         priority_queue<int,vector<int>,greater<int> > pq;
 5         int n=matrix.size();
 6         for(int i=0;i<n;i++){
 7             for(int j=0;j<n;j++){
 8                 pq.push(matrix[i][j]);
 9             }
10         }
11         int res;
12         for(int i=0;i<k;i++){
13             res=pq.top();
14             pq.pop();
15         }
16         return res;
17     }
18 };