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

传送门

思路：

1.对所有元素排序，时间复杂度：$O(n^{2}log{n}^2)$

class Solution { public: int kthSmallest(vector<vector<int>>& a, int k) { int cnt=0; vector<int>b; for(int i=0;i<a.size();i++) for(int j=0;j<a.size();j++) b.push_back(a[i][j]); sort(b.begin(),b.end()); return b[k-1]; } };

2.根据矩阵图形的性质可知，小于等于某一个数的图形在矩阵左上方，大于该数的部分在右下方，且左上角数最小，右下角数最大，因此考虑二分答案，从$a[n-1][0]$开始走，如果当前位置满足则$cnt+=(i+1),$该列满足条件的元素个数，否则$j++$，列数+1，直到走出矩阵。 时间复杂度：$O(nlog(r-l))$

class Solution { public: bool check(vector<vector<int>>& a,int mid,int k,int n){ int i=n-1,j=0,cnt=0; while(i>=0&&j<n){ if(a[i][j]<=mid){ cnt+=i+1; j++; } else i--; } return cnt>=k; } int kthSmallest(vector<vector<int>>& a, int k) { int n=a.size(),l=a[0][0],r=a[n-1][n-1]; while(l<r){ int mid=l+((r-l)>>1); if(check(a,mid,k,n)) r=mid; else l=mid+1; } return l; } };