package code; import java.util.Comparator; import java.util.PriorityQueue; /* * 378. Kth Smallest Element in a Sorted Matrix * 题意：在矩阵中搜索第k小的数，横轴和纵轴都是有序的 * 难度：Medium * 分类：Binary Search, Heap * 思路：两种思路。 1是类似多个有序链表合并的思路，优先队列。 * 2是二分，二分的是val，看比这个val小的数是不是k * Tips：lc23方法很像 * lc240, lc378 */ public class lc378 { class Cell{ int val, row, col; Cell(int v, int r, int c){ val = v; row = r; col = c; } } public int kthSmallest(int[][] matrix, int k) { PriorityQueue pq = new PriorityQueue(new Comparator() { @Override public int compare(Cell o1, Cell o2) { return o1.val-o2.val; } }); for (int i = 0; i < matrix.length ; i++) pq.add(new Cell(matrix[i][0], i, 0)); while(k>1){ Cell c = pq.remove(); if(c.col+1