current position:Home>Finding the k-th small element of ordered matrix (dichotomy idea)

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

2022-04-29 09:26:44Sword laii

 Insert picture description here

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

 Insert picture description here


class Solution {
    // 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 
    // Find each column <=target Element location of 
        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];
    // Find the leftmost boundary 
            int mid = left + (right-left)/2;
                right = mid;
                left = mid+1;
        return left;

copyright notice
author[Sword laii],Please bring the original link to reprint, thank you.

Random recommended