排序矩阵中的从小到大第k个数 · Kth Smallest Number In Sorted Matrix

［抄题］：

在一个排序矩阵中找从小到大的第 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;
    }
}

View Code