# 378. Kth Smallest Element in a Sorted Matrix

## August 20, 2016

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: You may assume k is always valid, 1 ≤ k ≤ n2.

/*solution 1,use heap,144ms,O(n^2 *  logk),k is the size of heap*/
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
priority_queue<int> heap;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[i].size();j++){
heap.emplace(matrix[i][j]);
if(heap.size()>k)
heap.pop();
}
}
return heap.top();
}
};


1. 大于或等于k,说明选择的mid太大，需要调整到左半区，则high=mid-1;
2. 小于k，说明我们选定的mid太小，需要调整到右半区，则low=mid+1;

/*solution 2,use binary-search,O(nlogn),56ms*/
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int low=matrix[0][0],n=matrix.size(),high=matrix[n-1][n-1],cnt=0,mid=low+((high-low)>>1);
while(low<=high){
mid=low+((high-low)>>1);
cnt=0;
for(int i=0;i<matrix.size();i++)
cnt=cnt+upper_bound(matrix[i].begin(),matrix[i].end(),mid)-matrix[i].begin();
if(cnt<k)
low=mid+1;
else
high=mid-1;
}
return low;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017