Lintcode401 Kth Smallest Number in Sorted Matrix solution 题解
发布在刷题能手——Lintcode 题解2018年4月12日view:299
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Find the kth smallest number in at row and column sorted matrix.

在一个排序矩阵中找从小到大的第 k 个整数。

排序矩阵的定义为:每一行递增,每一列也递增。

【题目链接】

www.lintcode.com/en/problem/kth-smallest-number-in-sorted-matrix/

【题目解析】

寻找第k小的数,可以联想到转化为数组后排序,不过这样的时间复杂度较高:O(n^2 log n^2) + O(k).

进一步,换种思路,考虑到堆(Heap)的特性,可以建立一个Min Heap,然后poll k次,得到第k个最小数字。不过这样的复杂度仍然较高。

考虑到问题中矩阵本身的特点:排过序,那么可以进一步优化算法。

[1 ,5 ,7],

[3 ,7 ,8],

[4 ,8 ,9],

因为行row和列column都已排序,那么matrix中最小的数字无疑是左上角的那一个,坐标表示也就是(0, 0)。寻找第2小的数字,也就需要在(0, 1), (1, 0)中得出;以此类推第3小的数字,也就要在(0, 1), (1, 0), (2, 0), (1, 1), (0, 2)中寻找。

在一个数字集合中寻找最大(Max)或者最小值(Min),很快可以联想到用Heap,在Java中的实现是Priority Queue,它的pop,push操作均为O(logn),而top操作,得到堆顶仅需O(1)。

从左上(0, 0)位置开始往右/下方遍历,使用一个Hashmap记录visit过的坐标,把候选的数字以及其坐标放入一个大小为k的heap中(只把未曾visit过的坐标放入heap),并且每次放入前弹出掉(poll)堆顶元素,这样最多会添加(push)2k个元素。时间复杂度是O(klog2k),也就是说在矩阵自身特征的条件上优化,可以达到常数时间的复杂度,空间复杂度也为O(k),即存储k个候选数字的Priority Queue (Heap)。

【参考答案】

www.jiuzhang.com/solutions/kth-smallest-number-in-sorted-matrix/

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏