378. 有序矩阵中第K小的元素
1.二分法
class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { auto n=matrix.size(); int l=matrix[0][0],r=matrix[n-1][n-1]; while(l<r) { int mi=l+(r-l)/2; if(check(matrix,mi,k,n)) r=mi; else l=mi+1; } return l; } bool check(vector<vector<int>>& v,int mid,int k,int n) { int x=n-1,y=0,cnt=0; while(x>=0&&y<n) { if(v[x][y]<=mid) { cnt+=(x+1); ++y; } else --x; } return cnt>=k; } }; 优先级队列 class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { struct point { point(int val,int xx,int yy):v(val),x(xx),y(yy) { } bool operator> (const point& r)const { return v>r.v; } int v; int x; int y; }; int n=matrix.size(); priority_queue<point,vector<point>,greater<point>>p; for(int i=0;i<n;++i) { p.emplace(matrix[i][0],i,0); } for(int i=1;i<k;++i) { auto tmp=p.top(); p.pop(); if(tmp.y<n-1) { p.emplace(matrix[tmp.x][tmp.y+1],tmp.x,tmp.y+1); } } return p.top().v; } };总结：
一般求第K大的数这种TOP k问题，可以考虑使用优先级队列，这道题里为了找到我们删除堆顶元素后的下一个元素，定义了一个point类辅助,如果是求n个链表的第k个数，那么就可以直接用堆保存链表节点。有序数组的相关问题考虑用二分法，难点在于找到二分法中的判断条件，本题中的check()函数。