最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含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]);

            }

        }

其他回答

可能的改进。

如果文件包含十亿的数字,读取它可能会很长…

为了提高工作效率,你可以:

将文件分成n个部分,创建n个线程,让n个线程在各自的部分中寻找最大的100个数字(使用优先级队列),最后得到所有线程输出的最大的100个数字。 使用像hadoop这样的解决方案,使用集群来完成这样的任务。在这里,您可以进一步分割文件,并更快地输出10亿(或10^12)个数字的文件。

Recently I am adapting a theory that all the problems in the world could be solved with O(1). And even this one. It wasn't clear from the question what is the range of the numbers. If the numbers are it range from 1 to 10, then probably the the top 100 largest numbers will be a group of 10. The chance that the highest number will be picked out of the 1 billion numbers when the highest number is very small in compare to to 1 billion are very big. So I would give this as an answer in that interview.

使用第n个元素得到第100个元素O(n) 迭代第二次,但只有一次,并输出大于此特定元素的所有元素。

请特别注意,第二步可能很容易并行计算!当你需要一百万个最大的元素时,它也会很有效。

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

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

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

我看到了很多O(N)的讨论,所以我提出了一些不同的想法。

关于这些数字的性质有什么已知的信息吗?如果答案是随机的,那就不要再进一步了,看看其他答案。你不会得到比他们更好的结果。

However! See if whatever list-populating mechanism populated that list in a particular order. Are they in a well-defined pattern where you can know with certainty that the largest magnitude of numbers will be found in a certain region of the list or on a certain interval? There may be a pattern to it. If that is so, for example if they are guaranteed to be in some sort of normal distribution with the characteristic hump in the middle, always have repeating upward trends among defined subsets, have a prolonged spike at some time T in the middle of the data set like perhaps an incidence of insider trading or equipment failure, or maybe just have a "spike" every Nth number as in analysis of forces after a catastrophe, you can reduce the number of records you have to check significantly.

不管怎样,还是有一些值得思考的东西。也许这会帮助你给未来的面试官一个深思熟虑的回答。我知道,如果有人问我这样一个问题来回应这样的问题,我会印象深刻——这将告诉我,他们正在考虑优化。只是要认识到,优化的可能性并不总是存在的。