- Question:
- Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
- Note that it is the kth smallest element in the sorted order, not the kth distinct element.
- Example:
- matrix = [[ 1, 5, 9],
- [10, 11, 13],
- [12, 13, 15]
- ],
- k = 8,
- return 13.
- Note:
- You may assume k is always valid, 1 k n2.
- Tips:
给定一个 n*n 的矩阵, 矩阵内每行跟每列都是升序排列的, 找到矩阵中第 k 小的元素, 并返回
解法:
思路 1:
要找到第 k 小的数字, 可以预先设定一个值 mid=low+(high-low)/2; 每次找到一个 mid, 然后求比它小的元素的个数, 根据个数大于 k 还是小于 k 来二分在寻找小于 mid 的元素个数的时候, 可以从左下或者右上开始查找, 例如从矩阵左下开始查找, 当前数字 > target 就可以删除该数字所在列的后面所有数字, row-- 如果当前数字 < target, 表示该行中, 该数字之前的所有数字均小于 target,col++;ans+=row+1;
代码 1:
- public int kthSmallest(int[][] matrix,int k){
- if(matrix==null ||matrix.length==0) return 0;
- int ans=0;
- int n=matrix.length;
- int low=matrix[0][0];
- int high=matrix[n-1][n-1];
- while(low<high){
- int mid=low+(low+high)/2;
- int count=binarysearch(matrix,mid);
- if(count>k){
- high=mid;
- }else
- low=mid+1;
- }
- return ans;
- }
- private int binarysearch(int[][] matrix, int target) {
- int ans=0;
- int len=matrix.length;
- int row=len-1;int col=0;
- while(row>=0 && col<len){
- if(matrix[row][col]>target)
- row--;
- else{
- col++;
- ans+=row;
- }
- }
- return ans;
- }
思路 2:
寻找第 k 小或第 k 大的元素均可以使用堆来解决本题要找到最小的第 k 个元素, 可以使用最大堆来完成堆的大小等于 k 是, 堆的 root 即为所要求,
代码 2:
- public int kthSmallest(int[][] matrix, int k) {
- // heap
- PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k + 1, (a, b) -> b - a);
- for(int i = 0; i < matrix.length; i++) {
- for(int j = 0; j < matrix[0].length; j++) {
- maxHeap.offer(matrix[i][j]);
- if(maxHeap.size() > k) maxHeap.poll();
- }
- }
- return maxHeap.poll();
- }
- Leetcode378. Kth Smallest Element in a Sorted Matrix
来源: http://www.bubuko.com/infodetail-2520941.html