D.二分查找－二分答案－第K小/第K大——378. 有序矩阵中第 K 小的元素

题目链接：378. 有序矩阵中第 K 小的元素（中等）

算法原理：

解法：二分查找+双指针

0ms击败100.00%

时间复杂度O(NlogN)

①目标变量：x

②目标条件：求最小x，使得≤x的数=k个

③转换逻辑：≤mid的数是否≥k个

具体步骤：

①确定边界：

left：matrix[0][0]，题目范围内，最小值为matrix[0][0]

right：matrix[n-1][n-1]，题目范围内，最大值为matrix[n-1][n-1]

②确定二分模型：x ↑ 比x小的数 ↑ 呈正相关单调，由于我们的目标是找最小的x，使得≤x的值≥k个，求最小，因此采用最左端点模型

③check方法设计：计算矩阵里≤mid的数量是否≥k，如何计算数量呢？

做法跟下题是一样的👇

A.每日一题——240. 搜索二维矩阵 II

图解如下👇

Java代码：

class Solution { public int kthSmallest(int[][] matrix, int k) { int n=matrix.length; int left=matrix[0][0],right=matrix[n-1][n-1]; while(left<right){ int mid=left+(right-left)/2; if(!check(mid,matrix,k)) left=mid+1; else right=mid; } return left; } //判断≤mid的数量是否≥k private boolean check(int mid,int[][] matrix,int k){ int m=matrix.length,cnt=0; int row=0,col=matrix[0].length-1; while(row<m&&col>=0){ if(matrix[row][col]<=mid){ cnt+=(col+1); row++; } else col--; } return cnt>=k; } }