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 ≤ n2

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

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

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

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据