有序矩阵+二分 378. 有序矩阵中第K小的元素

378. 有序矩阵中第K小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

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

返回 13。

提示： 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

大顶堆

class Solution { public: priority_queue<int> q; int kthSmallest(vector<vector<int>>& matrix, int k) { for(auto t:matrix) for(auto s:t){ if(k==q.size()&&s<q.top()) { q.pop(); q.push(s); } else if(q.size()<k) q.push(s); } return q.top(); } };

二分

有序矩阵遍历中线——上面小于自己，右边大于自己； 最小值为左上，最大值为右下；

最小值和最大值作为left和right二分； 每次找出小于等于mid 的数的个数； 若此个数大于等于k，则right=mid；（保留当前mid，且尝试往左找） 若个数i小于k，则left=mid+1；（舍弃当前mid，往右找） 最后找到的数一定满足小于等于该数的个数大于等于k；

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

如何保证找到的数在矩阵中

二分时最后找到的数num，小于等于num的数>=k个，小于等于num-1的数<k个，说明num肯定在矩阵中； 注意点 矩阵性质——z字形走，条件判断每一步的大小； 比期望值小则右边往大了找，比期望值大则左边往小了找；