每天一道leetcode378-有序矩阵中第K小的元素
- 2019 年 10 月 4 日
- 筆記
题目
leetcode378-有序矩阵中第K小的元素
英文链接：
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
中文链接：
https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
分类：二分查找类
题目详述
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。 请注意，它是排序后的第k小元素，而不是第k个元素。
示例:
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,返回 13。
说明: 你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。
暴力解决
思路
- 额，看到这个题目，一开始大体思路就是暴力解决；
- 遍历整个二维数组，然后把这个二维数组存到一个一维数组中，然后对这个一维数组，进行排序，然后取这个一维数组第k个值就行。
代码
class Solution { public int kthSmallest(int[][] matrix, int k) { if(matrix.length == 0 || matrix[0].length == 0) return -1; int rows = matrix.length; int cols = matrix[0].length; int number = rows * cols; int [] list = new int[number]; int count = 0; for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) { list[count] = matrix[i][j]; count++; } } Arrays.sort(list); return list[k-1]; } }
二分解决
思路
- 由于是一个矩阵，左上角的数是最小值，右下角的数是最大值，所以可以利用这一个特点来进行二分，每次取两个边界的值进行除以2，得到一个mid值；
- 然后根据这个mid值，统计整个矩阵中，小于mid值的个数，如果小于mid的值的个数刚好大于等于k个，那么说明应该缩小right的值到mid,如果小于k个，那么说明left应该变成mid；
- 这样一步步进行紧逼，找到最后的这个数据。
代码
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 + 1 < right) { int mid = (right - left) / 2 + left; int num = count(matrix, mid); if (num >= k) { right = mid; } else { left = mid; } } if (count(matrix, right) <= k - 1) return right; return left; } public int count(int[][] matrix, int target) { int n = matrix.length; int i = n - 1, j = 0; int res = 0; while (i >= 0 && j < n) { if (matrix[i][j] < target) { res += i + 1; //index + 1 = number of elements. j++; } else { i--; } } return res; } }
代码讲解
- 17行到30行代码就是求矩阵中小于target的数的大小，这里的话从第0列开始的最底层开始找，如果左下角的数比target小，那么说明这一列的数都是小于target所以，也就是出现了代码22行到24行，因为这个一列已经找过了，所以j++，移动到下一列去找；
- 如果左下角的数比target大，由于每一行递增，所以只能是i–,来去找下一行；以上就是对17行-30行代码的讲解
- 题目中使用了二分查找，去找最小值和最大值的中间值，如果小于中间值的个数是k个或者大于k个，那么让right去等于mid，往左边逼近；
- 如果小于中间值mid的个数是小于k的，那么说明不够k个，也就只能取把left变大，等于mid;
- 然后循环结束的条件是left+1<right;说明这时候结束的时候已经是left与right无限逼近了，这个时候left与right的中间值在数组里面（这里我也没有数学证明，left与right一直求中间值，那么最后中间值mid一定在数组里面？？？这个我自己试验了几个数组，确实是这样子，但是我数学能力有限，无法去证明，有人能证明吗，欢迎评论区留言）
结束语
2018.11.1打卡~
END
