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

2020-05-25

1.题目描述

有序矩阵中第K小的元素

2.题解

1.优先队列 2.使用二分查找 class Solution { public:int kthSmallest(vector<vector<int>>& matrix, int k) {priority_queue<int> myque; // 优先队列int l=matrix.size();for (int i=0;i<l;i++){for (int j=0;j<l;j++){myque.push(matrix[i][j]);if (myque.size()>k){myque.pop();if (matrix[i][j]>=myque.top()) break; // 跳出循环即可}}}return myque.top();} }; class Solution { public:int kthSmallest(vector<vector<int>>& matrix, int k) {int l=matrix.size();return midsort(matrix,k,l);}int midsort(vector<vector<int>> matrix,int k,int n){int l=matrix[0][0],h=matrix[n-1][n-1];while (l<h){int mid=(l+h)/2;int tmp=cnt(matrix,mid,n); // 统计小于等于当前值的元素的个数if (tmp<k) l=mid+1;else h=mid;}return l;}int cnt(vector<vector<int>> matrix,int value,int n){int x=n-1,y=0;int res=0;while (x>=0&&y<n){if (matrix[x][y]>value){x--;}else if (matrix[x][y]<=value){y++;res+=x+1;}}return res;} };

总结

以上是生活随笔为你收集整理的378. 有序矩阵中第K小的元素的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。