转载

LeetCode 第378题 Kth Smallest Element in a Sorted Matrix 【堆】java

原题地址: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

给定一个n x n的矩阵,每一行,每一列都是正序排列,寻找矩阵内的第k小元素。注意是指排序后的第k大元素,而不是第k个不重复元素。

例如:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13.

注意,你可以假定k永远合法,1 ≤ k ≤ n<sup>2</sup>。

这道题明显可以有更精巧的做法,因为提供了一些矩阵的特性。但是我最近在做堆有关的题目,所以暂时只提供一个堆的解,很无耻就是把矩阵展开成数组,然后构建最小堆,然后得解。代码如下:(堆相关代码,参加前文)
LeetCode 第378题 Kth Smallest Element in a Sorted Matrix 【堆】java

代码地址: https://github.com/tinyfool/leetcode/tree/master/src/p0378

也请参阅《 Leetcode专题 堆结构和堆排序 》,文章介绍了堆和堆排序,以及最大堆的实现。本题我们实现了一个最小堆,跟最大堆原理一样,只需要做几行修改即可。

原文  http://codechina.org/2019/07/leetcode-378-kth-smallest-element-in-a-sorted-matrix-java/
正文到此结束
Loading...