Cracking the coding interview--Q20.6
Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers.
译文：
描述一个算法，在10亿个数中找到最大的1百万个数。假设内存可以一次性装入这10亿个数。
解答
虽然这道题的数据量很大，但由于题目已经假设所有的数据可以一次性装入内存， 所以题目中的10亿，1百万也就没有什么特殊含义了。 我们完全可以想像成在100个数中查找最大的10个数。
这是一道经典的面试题，一般有以下几种解法：
排序法
最直观的方法就是将数组从大到小排序，然后取前1百万个数即可。时间复杂度O(nlogn)。
最小堆
利用最小堆来维护最大的1百万个数，堆顶元素是这1百万个数中最小的。 遍历剩下的元素，当某一元素大于堆顶元素，则用该元素替换堆顶元素， 然后调整堆结构，使其仍为最小堆。当遍历完所有10亿个数后， 堆中维护的就是最大的1百万个数。在n个数中查找最大的k个数，该算法需要O(nlogk) 的时间。由于k一般要比n小得多，所以该算法比排序法要快。
该算法还有一个优点，就是便于处理大数据。比如说， 我们一般需要在非常多的数中找到最大(最小)的k个数，这个k一般比较小， 而n却可能大得无法一次性载入内存。这时候我们就可以在内存中维护一个k 个元素的最小(最大)堆，然后把数据分多次从磁盘读入内存进行处理。
线性求k最大
线性求k最大利用的是快排中的partition函数。每次选取一个基准元素pivot (可以用第1个元素，也可以随机选)，然后将其它元素与pivot对比。大于等于pivot 的放到左边，小于pivot的放到右边。调用一次partition后， pivot左边的数都是大于等于它的，pivot右边的数都是小于它的。 如果pivot此时正好是第k-1个元素，那么它左边加上它一共有k个元素， 而且这k个元素都是比右边的元素要大的，即它们就是最大的k个元素。如果pivot 左边不足k-1个元素，则在它右边进行同样的partition操作。如果pivot 左边是多于k-1个元素的，则在它左边进行partition操作。
该算法会改变数组中元素的顺序，期望时间复杂度是O(n)。
Read full article from Cracking the coding interview--Q20.6
No comments:
Post a Comment