LeetCode 378.有序矩阵中第K小的元素

思路1.第k小/大问题的通用转化方法1第k小等价于求最小的x满足x的数至少有k个注意是至少不是恰好。2第k大等价于求最大的x满足x的数至少有k个注意是至少不是恰好。2.在本题中是找第k小的元素因此就是找最小的target满足 target的数至少有k个。因此target越大越能找到k个数target越小越不能找到k个数。据此可以二分猜答案。3.本题可以转化为给定整数target统计有序矩阵中 target的元素个数cnt判断是否满足cnt k。4.如何做到高效统计cnt通过双指针实现如下图所示。5.细节本代码中采用闭区间二分使用开区间或者半开半闭区间也是可以的。1闭区间左端点的初始值matrix[0][0]。由于不会存在比最小值还小的数也就是有0个数 matrix[0][0]由于0 k所以无法满足要求。2闭区间右端点的初始值matrix[n - 1][n - 1]有n^2个数 matrix[n - 1][n - 1]由于n^2 k所以一定满足要求。3二分查找寻找第k小的元素。如果矩阵中 mid的元素个数 k那么第k小的元素一定 mid。此时记录mid作为一个候选答案我们还要继续向左寻找看能否找到更小的满足条件的值。最终返回的就是最小的满足条件的mid。6.疑问为什么二分结束后答案ans一定在矩阵中答虽在在过程中ans记录的可能不是矩阵中的元素但由于我们不断缩小范围最终会下降到矩阵中实际存在的元素这是因为任何不在矩阵中的元素x如果它满足小于等于它的数cnt k那么比它小的下一个矩阵元素也一定满足cnt k。因此二分最终会收敛到矩阵中实际存在的数字。所以ans最终就是矩阵中第k小的元素。7.复杂度分析1时间复杂度O(nlog(U))。其中n是matrix的行数和列数U matrix[n - 1][n - 1] - matrix[0][0]。二分O(log(U))次每次需要跑一个O(n)的双指针。2空间复杂度O(1)。附代码class Solution { public int kthSmallest(int[][] matrix, int k) { int n matrix.length; int left matrix[0][0]; int right matrix[n - 1][n - 1]; int ans -1; while (left right) { int mid left (right - left) / 2; // 说明矩阵中 mid的元素个数 k // 说明第k小的元素一定 mid if (check(matrix,mid,k)) { // 此时记录的mid是一个候选答案 ans mid; // 缩小范围继续往左边找看能否找到更小的满足条件的值 right mid - 1; } else { // 不满足条件就向右找 left mid 1; } } // 最终返回最小的满足条件的值 return ans; } private boolean check(int[][] matrix,int target,int k) { int n matrix.length; int cnt 0; // matrix中的 target的元素个数 int i 0; int j n - 1; // 从右上角开始 while (i n j 0 cnt k) { if (matrix[i][j] target) { j--; // 排除第j列 } else { cnt j 1; // 说明整行元素都 targetcnt加上这行元素的个数 i; // 第i行加完也排除 } } return cnt k; // 判断matrix中的 target的元素个数是否 k } }ACM模式import java.util.Scanner; class Solution { public int kthSmallest(int[][] matrix, int k) { int n matrix.length; int left matrix[0][0]; int right matrix[n - 1][n - 1]; int ans -1; while (left right) { int mid left (right - left) / 2; if (check(matrix,mid,k)) { ans mid; right mid - 1; } else { left mid 1; } } return ans; } private boolean check(int[][] matrix,int target,int k) { int n matrix.length; int cnt 0; int i 0; int j n - 1; while (i n j 0 cnt k) { if (matrix[i][j] target) { j--; } else { cnt j 1; i; } } return cnt k; } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取矩阵大小 int n scanner.nextInt(); // 读取矩阵 int[][] matrix new int[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { matrix[i][j] scanner.nextInt(); } } int k scanner.nextInt(); // 计算第k小的元素 Solution solution new Solution(); int result solution.kthSmallest(matrix, k); System.out.println(result); scanner.close(); } }