leetcode-378-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:

1
2
3
4
5
6
7
8
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, $1 ≤ k ≤ n^2$.

分析

这个题目要求找到第 k 小的元素，但数组并非规则的有序排列，也就是说没法按照顺序遍历数组。如果使用最大堆解决这个问题会比较简单，遍历二元数组中的所有元素，将其加入堆中，如果堆的大小超过 k，将其中最大的元素拿到，也就是执行一次 poll 操作。最后留下的堆中，最大的数字是第 k 小的元素。

看讨论里，使用 Java 解决这个问题的，也有用优先队列的，但代码都好啰嗦的样子。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue <Integer>(matrix.length*matrix.length, Collections.reverseOrder());
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                heap.add(matrix[i][j]);
                if (heap.size() > k) {
                    heap.poll();
                }
            }
        }
        return heap.peek();
    }
}

相关问题

题目来源