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

原题链接：

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

https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/description/

完成情况：

解题思路：

参考代码：

__378有序矩阵中第K小的元素__直接排序

package 西湖算法题解___中等题;import java.util.Arrays;public class __378有序矩阵中第K小的元素__直接排序 {public int kthSmallest(int[][] matrix, int k) {/*给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。*/int rows = matrix.length;   //行rowint cols = matrix[0].length;    //列colint sorted [] = new int[rows * cols];   //组合成一排数组，进行排序int index = 0;for (int row [] : matrix){      //每次获取matrix里的int row [] 数据for (int num : row){    //同时再在每一行row[]获取到每一个数sorted[index++] = num;}}Arrays.sort(sorted);return sorted[k-1];}
}

__378有序矩阵中第K小的元素__归并排序

package 西湖算法题解___中等题;import java.util.Comparator;
import java.util.PriorityQueue;public class __378有序矩阵中第K小的元素__归并排序 {public int kthSmallest(int[][] matrix, int k) {PriorityQueue<int []> priorityQueue = new PriorityQueue<int []>(new Comparator<int[]>() {@Overridepublic int compare(int[] a, int[] b) {return a[0] - b[0];}});//--------------------------------------------------------------------------int n = matrix.length;for (int i = 0;i<n;i++){priorityQueue.offer(new int[]{matrix[i][0],i,0});}//--------------------------------------------------------------------------for (int i = 0;i<k-1;i++){int  now [] = priorityQueue.poll();if (now[2] != n -1){priorityQueue.offer(new int[]{matrix[now[1]][now[2] + 1],now[1],now[2]+1});}}return priorityQueue.poll()[0];}
}

__378有序矩阵中第K小的元素__二分查找

package 西湖算法题解___中等题;public class __378有序矩阵中第K小的元素__二分查找 {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) >> 1 ) ;if (myCheck(matrix,mid,k,n)){right = mid;}else {left = mid + 1;}}return left;}private boolean myCheck(int[][] matrix, int mid, int k, int n) {int i = n-1;int j = 0;int num = 0;while (i >= 0 && j<n){if (matrix[i][j] <= mid){num += (i+1);j++;}else {i--;}}return num >= k;}
}