Leetcode 378. 有序矩阵中第 K 小的元素 二分查找

原题链接：Leetcode 378. 有序矩阵中第 K 小的元素

解题思路：

参考自博客：LeetCode题练习与总结：有序矩阵中第 K 小的元素–378

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n=matrix.size();
        int l=matrix[0][0];
        int r=matrix[n-1][n-1];
        while(l<r){
            int mid=l+(r-l)/2;
            int j=n-1;
            int cnt=0;
            for(int i=0;i<n;i++){
                while(j>=0 && matrix[i][j]>mid){
                    j--;
                }
                cnt+=(j+1);
            }
            if(cnt<k){
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        return l;
    }
};

为什么left一定在矩阵中？

• 循环过程中，矩阵中第k小的那个数始终在区间[left, right]中

• 循环过程中，left和right可能不是矩阵中的元素，但是[left, right]中某个元素 ”在矩阵中“ 且 ”满足第k小“

• 当right == left时，[left, right]中只有一个元素了(即left)，所以此时left必然 ”在矩阵中“ 且
  ”满足第k小“

此题的完整流程+过程演示：

#include <iostream>
#include <vector>
using namespace std;

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n=matrix.size();
    int l=matrix[0][0];
    int r=matrix[n-1][n-1];
    int round=1;
    while(l<r){
        cout<<"第" <<round<<"次查找："<<endl;
        cout<<"开始时：" <<endl;
        int mid=l+(r-l)/2;
        int j=n-1;
        int cnt=0;
        cout<<"left:"<<l<<endl;
        cout<<"right:"<<r<<endl;
        cout<<"mid:"<<mid<<endl;
        for(int i=0;i<n;i++){
            while(j>=0 && matrix[i][j]>mid){
                j--;
            }
            cnt+=(j+1);
        }
        if(cnt<k){
            l=mid+1;
        }
        else{
            r=mid;
        }
        round++;
        cout<<"找到" <<cnt<<"个小于等于mid的数"<<endl;
        cout<<"更新后："<<endl;
        cout<<"left:"<<l<<endl;
        cout<<"right:"<<r<<endl;
        cout<<"------------------------------------------------------"<<endl;
    }
    return l;
}

int main()
{
    vector<vector<int>> mat;
    mat.push_back({1,5,9});
    mat.push_back({10,11,13});
    mat.push_back({12,13,15});
    int res=kthSmallest(mat, 8);
    cout<<res<<endl;
    return 0;
}

第1次查找：
开始时：
left:1
right:15
mid:8
找到2个小于等于mid的数
更新后：
left:9
right:15
------------------------------------------------------
第2次查找：
开始时：
left:9
right:15
mid:12
找到6个小于等于mid的数
更新后：
left:13
right:15
------------------------------------------------------
第3次查找：
开始时：
left:13
right:15
mid:14
找到8个小于等于mid的数
更新后：
left:13
right:14
------------------------------------------------------
第4次查找：
开始时：
left:13
right:14
mid:13
找到8个小于等于mid的数
更新后：
left:13
right:13
------------------------------------------------------
13