中建八局第一建设有限公司税号_微分销系统bh_今日头条新闻最全新消息_搜外网

原题链接：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