用户浏览网站的习惯,网站建设公司固定ip,鲜花网络营销推广方案,新泰建设局网站378. 有序矩阵中第 K 小的元素 原题链接#xff1a;完成情况#xff1a;解题思路#xff1a;参考代码#xff1a;__378有序矩阵中第K小的元素__直接排序__378有序矩阵中第K小的元素__归并排序__378有序矩阵中第K小的元素__二分查找 原题链接#xff1a;
378. 有序矩阵中… 378. 有序矩阵中第 K 小的元素 原题链接完成情况解题思路参考代码__378有序矩阵中第K小的元素__直接排序__378有序矩阵中第K小的元素__归并排序__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) {PriorityQueueint [] priorityQueue new PriorityQueueint [](new Comparatorint[]() {Overridepublic int compare(int[] a, int[] b) {return a[0] - b[0];}});//--------------------------------------------------------------------------int n matrix.length;for (int i 0;in;i){priorityQueue.offer(new int[]{matrix[i][0],i,0});}//--------------------------------------------------------------------------for (int i 0;ik-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 jn){if (matrix[i][j] mid){num (i1);j;}else {i--;}}return num k;}
}
