面试题[堆排序]: 二维数组的Top(N)
浏览数：22 /
时间：2015年06月08日
题目：一个二维数组，每一行都是升序排列的，但每一列每一列并不一定是升序排列的，设计算法找出最大的N个数。
这类Top(N)算法，很容易想到堆排序，那么建什么堆呢？建多大的堆呢？
这个题目有个特点就是矩阵的最后一列是每一行的最大元素，那么整个矩阵的最大元素必然也在最后一列，所以我们可以考虑将最后一列元素建一个大根堆，建好之后，堆顶就是目前最大的元素，pop出最大的元素之后，将该最大元素的所在行的前一个元素放入对顶，并调整为大根堆，循环N次操作即可得到Top(N)个元素。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
