# Finding the k-th small element of ordered matrix (dichotomy idea)

2022-04-29 09:26:44

Their thinking
Two points search , Convert two dimensions to one dimension ,check The function is used to solve less than or equal to target The number of elements is the same as k The relationship between

Code

``````class Solution {

public:
// Statistical satisfaction less than target Number of array elements , exceed k return true, Not more than k return false
bool check(vector<vector<int>>& matrix, int cnt,int target,int k){

int num = 0;
int i = cnt-1;
int j = 0;
while(i>=0 && j<cnt){
// Start at the lower left corner of the matrix , And statistics of the second j Column to the first i Number of elements in the row
if(matrix[i][j]<=target){
// Find each column <=target Element location of
j++;
num+=i+1;
}else{

i--;
}
}
return num>=k;
}

// Two points search
int kthSmallest(vector<vector<int>>& matrix, int k) {

int cnt = matrix.size();
int left = matrix[0][0];
int right = matrix[cnt-1][cnt-1];
while(left<right){
// Find the leftmost boundary
int mid = left + (right-left)/2;
if(check(matrix,cnt,mid,k)){

right = mid;
}else{

left = mid+1;
}
}
return left;
}
};

``````