最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。

我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。

Arrays.sort(array);

面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?


当前回答

我做了我自己的代码,不确定它是否是“面试官”所寻找的

private static final int MAX=100;
 PriorityQueue<Integer> queue = new PriorityQueue<>(MAX);
        queue.add(array[0]);
        for (int i=1;i<array.length;i++)
        {

            if(queue.peek()<array[i])
            {
                if(queue.size() >=MAX)
                {
                    queue.poll();
                }
                queue.add(array[i]);

            }

        }

其他回答

你可以遍历这些数字,需要O(n)

只要发现一个大于当前最小值的值,就将新值添加到一个大小为100的循环队列中。

循环队列的最小值就是新的比较值。继续往队列中添加。如果已满,则从队列中提取最小值。

虽然其他的quickselect解决方案已经被否决,但事实是quickselect将比使用大小为100的队列更快地找到解决方案。在比较方面,Quickselect的预期运行时间为2n + o(n)。一个非常简单的实现是

array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
  if(array[i]>r)
     add array[i] to result

这平均需要3n + o(n)次比较。此外,quickselect将数组中最大的100个项保留在最右边的100个位置,这可以提高效率。所以实际上,运行时间可以提高到2n+o(n)。

有一个问题是,这是预期的运行时间,而不是最坏的情况,但通过使用一个不错的主元选择策略(例如,随机选择21个元素,并选择这21个元素的中位数作为主元),那么比较的数量可以保证高概率为(2+c)n对于任意小的常数c。

事实上,通过使用优化的抽样策略(例如随机抽样平方根(n)个元素,并选择第99百分位数),对于任意小的c(假设K,要选择的元素数量为o(n)),运行时间可以降至(1+c)n + o(n)。

另一方面,使用大小为100的队列将需要O(log(100)n)个比较,log以2为底100的对数大约等于6.6。

如果我们从更抽象的意义上考虑这个问题,即从大小为N的数组中选择最大的K个元素,其中K=o(N),但K和N都趋于无穷大,那么快速选择版本的运行时间将是o(N),队列版本的运行时间将是o(N log K),因此在这种意义上,快速选择也渐近地更好。

在注释中,提到队列解决方案将在随机输入的预期时间N + K log N内运行。当然,随机输入假设永远不会成立,除非问题明确地说明了这一点。队列解决方案可以以随机顺序遍历数组,但这将产生对随机数生成器的N次调用的额外成本,以及排列整个输入数组或分配一个长度为N的包含随机索引的新数组。

如果问题不允许您移动原始数组中的元素,并且分配内存的成本很高,因此不能复制数组,那就是另一回事了。但严格地从运行时间来看,这是最好的解决方案。

两个选择:

(1)堆(priorityQueue)

维护最小堆的大小为100。遍历数组。一旦元素小于堆中的第一个元素,就替换它。

InSERT ELEMENT INTO HEAP: O(log100)
compare the first element: O(1)
There are n elements in the array, so the total would be O(nlog100), which is O(n)

(2)映射-约简模型。

这与hadoop中的单词计数示例非常相似。 映射工作:计算每个元素出现的频率或次数。 减约:获取顶部K元素。

通常,我会给招聘人员两个答案。他们喜欢什么就给什么。当然,映射缩减编码会很费事,因为您必须知道每个确切的参数。练习一下也无妨。 祝你好运。

首先取1000个元素并将它们添加到一个max堆中。现在取出前最多100个元素并将其存储在某个地方。现在从文件中选择接下来的900个元素,并将它们与最后100个最高的元素一起添加到堆中。

一直重复这个过程,从堆中取出100个元素,从文件中添加900个元素。

从100个元素中最后选出的100个元素将从10亿个数字中选出最大的100个元素。

如果在面试中被问到这个问题,面试官可能想看你解决问题的过程,而不仅仅是你的算法知识。

The description is quite general so maybe you can ask him the range or meaning of these numbers to make the problem clear. Doing this may impress an interviewer. If, for example, these numbers stands for people's age then it's a much easier problem. With a reasonable assumption that nobody alive is older than 200, you can use an integer array of size 200 (maybe 201) to count the number of people with the same age in just one iteration. Here the index means the age. After this it's a piece of cake to find 100 largest numbers. By the way this algorithm is called counting sort.

无论如何,让问题更具体、更清楚对你在面试中是有好处的。