原题目：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; } };
