378. 有序矩阵中第K小的元素 k路归并+二分法

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

难度：中等 2020/7/2每日一题打卡√ 题目描述 解题思路

1、直接用优先队列

简单直接无脑

/* * 378. 有序矩阵中第K小的元素 * 2020/7/2 类似于合并k个有序列表 */ public int kthSmallest(int[][] matrix, int k) { if(k == 1) return matrix[0][0]; int n = matrix.length; PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); for (int i = 0; i < n; i++) { for (int j = 0; j < matrix.length; j++) { if(maxHeap.size() < k) { maxHeap.offer(matrix[i][j]); }else if(matrix[i][j] < maxHeap.peek()) { maxHeap.poll(); maxHeap.offer(matrix[i][j]); } } } return maxHeap.peek(); }

2、二分法

题目里没有明显的二分条件，就自己创造二分条件。对于这道题，数组里元素的范围其实是给出来的，左上角元素最小，右下角元素最大，在这个范围内即性二分查找。查找的条件是对于mid，计算数组里元素小于mid的个数，如果个数小于k，说明第k小的元素出现在右半区间，收缩左端点。 如果大于mid的个数，说明mid范围大了，收缩左端点。 问题是最后怎么确定得到的left一定出现在数组里。 自己举个例子就能知道，比如说第k小的数字是15，当mid = 15的时候才刚好满足条件，left此时也等于15

//二分法 public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int left = matrix[0][0]; int right = matrix[n-1][n-1]; while(left < right) { int mid = left + (right-left)/2; if(checkLessThanK(matrix, mid) < k) { //如果比 mid小的数字小于k个 left = mid + 1; }else { right = mid; } } return left; } //检查到mid为止小于k的数字个数 public int checkLessThanK(int[][] matrix,int mid) { int count = 0,n = matrix.length; for (int i = 0; i < n; i++) { if(matrix[i][n-1] <= mid) { count += n; }else { for (int j = 0; j < n; j++) { if(matrix[i][j] <= mid) { count++; } } } } return count; }

3、用k路归并排序的思路

这个矩阵的每一行均为一个有序数组。问题即转化为从这 n 个有序数组中找第 k 大的数，可以想到利用归并排序的做法，归并到第 k 个数即可停止。

一般归并排序是两个数组归并，而本题是 n 个数组归并，所以需要用小根堆维护，以优化时间复杂度。

/* * 378. 有序矩阵中第K小的元素 * 2020/7/2 类似于合并k个有序列表 */ public int kthSmallest(int[][] matrix, int k) { if(k == 1) return matrix[0][0]; int n = matrix.length; PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]); for (int i = 0; i < n; i++) { //先把第一列所有元素加入到优先队列里，保存行列信息 pq.offer(new int[] {matrix[i][0],i,0}); } for (int i = 0; i < k-1; i++) { //归并到第k个元素时停止 int[] temp = pq.poll(); if(temp[2]+1 < n) { //把最小值后面的那个元素入队 int p = temp[1],q = temp[2]+1; pq.offer(new int[] {matrix[p][q],p,q}); } } return pq.peek()[0]; }