小根堆

• 堆中不重复放（就是原矩阵中之前已经放进过堆的，不再重复放）

// 放入堆中的节点
public static class Node {
  public int value;
  public int row;
  public int col;
  public Node(int value, int row, int col) {
    this.value = value;
    this.row = row;
    this.col = col;
  }
}
// 小根堆
public static class NodeComparator implements Comparator<Node> {
  @Override
  public int compare(Node o1, Node o2) {
    return o1.value - o2.value;
  }
}
public int kthSmallest(int[][] matrix, int k) {
    int N = matrix.length;
    int M = matrix[0].length;
    PriorityQueue<Node> heap = new PriorityQueue<>(new NodeComparator());
    boolean[][] set = new boolean[N][M];
    //左上角的值是最小的
    heap.add(new Node(matrix[0][0], 0, 0));
    set[0][0] = true;
    int count = 0;
    Node ans = null;
    while (!heap.isEmpty()) {
      ans = heap.poll();
      if (++count == k) {
        break;
      }
      int row = ans.row;
      int col = ans.col;
      if (row + 1 < N && !set[row + 1][col]) {
        heap.add(new Node(matrix[row + 1][col], row + 1, col));
        set[row + 1][col] = true;
      }
      if (col + 1 < M && !set[row][col + 1]) {
        heap.add(new Node(matrix[row][col + 1], row, col + 1));
      }
    }
    return ans.value;
}