378. Kth Smallest Element in a S

题目分析

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.

TopK的问题都可以考虑用 PriorityQueue 来做，这个题还可以用 Bianry Search 来做。首先说明一下这个题的意思是说矩阵元素按行是升序的，按列是升序的。找出矩阵中的第 K 小的元素。

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // lambda 表达式写法
        PriorityQueue<Tuple> pq = new PriorityQueue<>(matrix.length, (a, b) -> (a.val - b.val));
        // matrix 第一行的元素入队
        for(int i = 0; i < matrix.length; i++) {
            pq.offer(new Tuple(0, i, matrix[0][i]));
        }
        // 找第 K 小，那么 pop K - 1 次即可
        for(int i = 0; i < k - 1; i++) {
            Tuple tuple = pq.poll();
            // 边界判断，是不是已经在最后一行了
            if(tuple.x == matrix.length - 1) continue;
            pq.offer(new Tuple(tuple.x + 1, tuple.y, matrix[tuple.x + 1][tuple.y]));
        }
        return pq.poll().val;
    }        
}

class Tuple {
    int x;
    int y;
    int val;
    public Tuple(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}