Cracking the coding interview--Q20.6

March 3, 2013
作者:Hawstein
出处:http://hawstein.com/posts/20.6.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

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)。

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview