Kth Smallest Element in a Sorted Matrix

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.

思路

1. 用最大堆来做，最大堆的顺序是从大到小，5, 4, 3 ,2,1, 弹出时也是一次5，4，3，2，1，的顺序弹出。
2. 维护一个大小为k的最大堆，为保证堆顶的元素就是Kth smallest，所以当maxHeap.size() >k时，弹出堆顶元素。
3. 最后堆顶元素就是Kth smallest element

public class Solution {
   /*
    * @param matrix: a matrix of integers
    * @param k: An integer
    * @return: the kth smallest number in the matrix
    */
   public int kthSmallest(int[][] matrix, int k) {
       // write your code here
       // 用最大堆来做，最大堆的顺序是从大到小，5, 4, 3 ,2,1, 弹出时也是一次5，4，3，2，1，的顺序弹出
       
       
       PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, (o1, o2)-> o2 - o1);
       
       for (int i = 0; i < matrix.length; i++) {
           for (int j = 0; j < matrix[0].length; j++) {
               maxHeap.offer(matrix[i][j]);
               //当堆size大于k时，把堆顶的元素弹出。这样保证，最后堆顶的就是kth smallest
               if (maxHeap.size() > k) {
                   maxHeap.poll();
               }
           }
       }
       
       return maxHeap.poll();
   }
}