原题

378.有序矩阵中第K小的元素 2020年7月2日 每日一题

题解

方法一

基本思路就是把矩阵中的所有元素都放进一个数组里面或者一个ArrayList里面，之后按照升序排序，再取出编号为k-1的那个数。 本思路java代码示例：

/* @v7fgg 执行用时：25 ms, 在所有 Java 提交中击败了21.18%的用户 内存消耗：44.5 MB, 在所有 Java 提交中击败了15.38%的用户 2020年7月2日 7:36 */ class Solution { public int kthSmallest(int[][] matrix, int k) { List<Integer> ans=new ArrayList<>(); for(int i=0;i<matrix.length;i++){ for(int j=0;j<matrix[0].length;j++){ ans.add(matrix[i][j]); } } Collections.sort(ans); return ans.get(k-1); } }

方法二 二分法

/*二分法 @v7fgg 非原创，改编自官解 执行用时：1 ms, 在所有 Java 提交中击败了74.03%的用户 内存消耗：45.3 MB, 在所有 Java 提交中击败了7.69%的用户 2020年7月2日 9:39 */ class Solution { public int kthSmallest(int[][] matrix, int k) { //zuo和you分别确定寻找的范围 int zuo=matrix[0][0]; int you=matrix[matrix.length-1][matrix.length-1]; while(zuo<you){ int mid=(zuo+you)/2; int nSmaller=0; int l=0; int r=matrix.length-1; //是从左下角开始 while(l<matrix.length&&r>=0){ if(matrix[r][l]<=mid){ //说明这一列有不大于mid的数字，那就把这些数字的个数加起来 nSmaller+=r+1; l++;//同时下一个寻找的时候要增大，也就是列要往右 } //否则说明这一列里面r行位置是大于mid的应该上移重新找 else{r--;} } if(nSmaller<k){zuo=mid+1;} else{you=mid;} } return zuo; } }

方法二参考资料1