原题目:https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
思路一:
使用大顶堆,找出前k小。
代码:
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
priority_queue<int> q;
int n = matrix.size();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
q.push(matrix[i][j]);
while(q.size()>k){
q.pop();
}
}
}
return q.top();
}
};
思路二:
二分查找,找出小于mid的数目,如果此数目大于等于k,那么就在小于mid的数里面继续找,否则在大于 mid的数里面继续寻找。
数目怎么查找?我们可以分析发现,因为每行每列都是升序的,所以小于mid的数一定位于其左上角,则如下图所示(来源于leetcode):
class Solution {
public:
int count(vector<vector<int>>& matrix, int n ,int c){
int num = 0;
int i = n-1,j=0;
while(i>=0 && j<n){
if(matrix[i][j]<=c){
num += i+1;
j++;
}
else{
i--;
}
}
return num;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int left = matrix[0][0];
int right = matrix[n-1][n-1];
while(left<=right){
int mid = left + (right - left) / 2;
if(count(matrix,n,mid) >= k) right = mid - 1;
else left = mid + 1;
}
return left;
}
};