［抄题］：
在一个排序矩阵中找从小到大的第 k 个整数。
排序矩阵的定义为：每一行递增，每一列也递增。
［思维问题］：
不知道应该怎么加，因为不是一维单调的。
［一句话思路］：
周围两个数给x或y挪一位, 如果hash数组没有就添加到minheap中
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- class Pair(没有参数)中要有数据类型、方法Pair(int x , int y, int val)
- PairComparator 继承了 Comparator<Pair>类 里面自然就是对pair进行比较, 接口<内容物>＋名 ＝ new 内部结构名<内容物>。Queue xx = new PQ<Integer>(k,新建pair对象) 0,0,matrix[0][0] 也要新建对象 new Pair
- x坐标用dx表示, 里面只有0，1
- 取出数从i = 1开始，不用从0开始。因为第一个符合条件的pair是(0,0,matrix[0][0])。
- 数组不包括，直接用!hash[x][y]即可
［二刷］：
- class关键字是小写开头
- next_pair新建之后，minheap直接add(next_pair)即可
- dx,dy数组的作用是加一位坐标，因此里面有东西：0 或 1
［三刷］：
- paircomparator类是继承来的，别的地方可以用，所以写class
［四刷］：
［五刷］：
［总结］：
［复杂度］：Time complexity: O(klgk) Space complexity: O(k)
［英文数据结构，为什么不用别的数据结构］：
heap符合每次取顶 丢掉，取到k个为止
［其他解法］：
二分法
［Follow Up］：
［LC给出的题目变变变］：
373. Find K Pairs with Smallest Sums 也是用minheap实现取最小
668. Kth Smallest Number in Multiplication Table 看着像用heap，其实用二分法 玩数学
719. Find K-th Smallest Pair Distance 其实用二分法 玩数学。看来二分法也能用于查找最小的第k个数
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) {
class Pair {
int x,y,val;
public Pair(int x,int y,int val) {
this.x = x;
this.y = y;
this.val = val;
}
};
class PairComparator implements Comparator<Pair>{
public int compare(Pair a,Pair b) {
return a.val - b.val;
}
};
int m = matrix.length;
int n = matrix[0].length;
int[] dx = new int[]{0,1};
int[] dy = new int[]{1,0};
boolean[][] hash = new boolean[m][n];
Queue<Pair> minHeap = new PriorityQueue<Pair>(k,new PairComparator());
minHeap.add(new Pair(0,0,matrix[0][0]));
for (int i = 1; i < k; i++) {
Pair cur = minHeap.poll();
for (int j = 0; j < 2; j++) {
int next_x = cur.x + dx[j];
int next_y = cur.y + dy[j];
Pair next_Pair = new Pair(next_x,next_y,0);
if (next_x < m && next_y < n && !hash[next_x][next_y]) {
next_Pair.val = matrix[next_x][next_y];
hash[next_x][next_y] = true;
minHeap.add(next_Pair);
}
}
}
return minHeap.peek().val;
}
}