归并排序
class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { int n=matrix.size(); vector<int> res(n*n,0); int * l=& matrix[0][0]; for(int st=0;st<n;st++) res[st]=*(l++); int len=0; int t=1; while(t<n){ len=len+n; int left[len]; for(int m=0;m<len;m++) left[m]=res[m]; int *right=& matrix[t][0]; int ki=0,i=0,j=0; while(i<len&& j<n){ if(left[i]<right[j]){ res[ki++]=left[i]; i++; } else{ res[ki++]=right[j]; j++; } } while(i<len) res[ki++]=left[i++]; while(j<n) res[ki++]=right[j++]; t++; } return res[k-1]; } }; ` class Solution { public: int numOfLeMid(vector<vector<int>> & matrix,int mid){ int n=matrix.size(); int i=n-1,j=0; int sum=0; while(i>=0&&j<n){ if(matrix[i][j]<=mid) { sum+=i+1; j++; } else i--; } return sum; } int kthSmallest(vector<vector<int>>& matrix, int k) { int L=matrix[0][0]; int n=matrix.size(); int R=matrix[n-1][n-1]; while(L<R){ int mid=L+((R-L)>>2); if(numOfLeMid(matrix,mid)<k) L=mid+1; else R=mid; } return L; } }; class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { int n=matrix.size(); struct point{ int val,x,y; point(int val,int x,int y){ this->val=val; this->x=x; this->y=y; } bool operator >(const point &a) const { return this->val>a.val;} }; priority_queue<point,vector<point>,greater<point>> que; for(int i=0;i<n;i++){ point a (matrix[0][i],0,i); que.push(a); } for(int j=0;j<k-1;j++){ point temp=que.top(); que.pop(); if(temp.x<n-1) que.push(point (matrix[temp.x+1][temp.y],temp.x+1,temp.y)); } return que.top().val; } };堆排序
class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { int n=matrix.size(); struct point{ int val; point(int val){ this->val=val; } bool operator >(const point &a) const { return this->val>a.val;} }; priority_queue<point,vector<point>,greater<point>> que; vector<int>res(n*n,0); int i,j; for(i=0;i<n;i++){ for (j=0;j<n;j++) que.push(point (matrix[i][j])); } for(j=0;j<k-1;j++) que.pop(); return que.top().val; } };斜体样式
