赞
踩
- //从左下角进行遍历,和之前那个找是否存在某个元素(右上角开始搜索)相反
- class Solution {
- public:
- int kthSmallest(vector<vector<int>>& matrix, int k) {
- int left=matrix[0][0],right=matrix.back().back();
- while(left<right){
- //int mid=(left+right)/2;
- int mid= left+ (right-left)/2;
- int index=search(matrix,mid);
- if(index<k)
- left=mid+1;
- else
- right=mid;
- }
- return left;
- }
- int search(vector<vector<int>>& matrix, int mid){
- int i=matrix.size()-1, j=0,cnt=0; //从左下角开始
- while(i>=0&&j<matrix[0].size()){
- if(matrix[i][j]<=mid){ //也是先从列开始
- j+=1;
- cnt += i+1; //那个元素所在的整列元素都小于 target。i的index从0开始的,所以要+1
- }else{ //再从行开始
- i-=1;
- }
- }
- return cnt;
- }
- };

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。