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

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

Arrays.sort(array);

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


当前回答

I would find out who had the time to put a billion numbers into an array and fire him. Must work for government. At least if you had a linked list you could insert a number into the middle without moving half a billion to make room. Even better a Btree allows for a binary search. Each comparison eliminates half of your total. A hash algorithm would allow you to populate the data structure like a checkerboard but not so good for sparse data. As it is your best bet is to have a solution array of 100 integers and keep track of the lowest number in your solution array so you can replace it when you come across a higher number in the original array. You would have to look at every element in the original array assuming it is not sorted to begin with.

其他回答

简单的解决方案是使用优先队列,将前100个数字添加到队列中,并跟踪队列中最小的数字,然后遍历其他10亿个数字,每当我们发现一个比优先队列中最大的数字大的数字时,我们删除最小的数字,添加新的数字,并再次跟踪队列中最小的数字。

如果这些数字是随机顺序的,这就很好了,因为当我们迭代10亿个随机数字时,下一个数字是目前为止最大的100个数字之一的情况是非常罕见的。但这些数字可能不是随机的。如果数组已经按升序排序,则始终向优先队列插入一个元素。

我们先从数组中选取100,000个随机数。为了避免可能很慢的随机访问,我们添加了400个随机组,每个组有250个连续的数字。通过这种随机选择,我们可以非常确定,剩下的数字中很少有进入前100位的,因此执行时间将非常接近于一个简单的循环,将10亿个数字与某个最大值进行比较。

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

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个

考虑所有的百万数字的二进制表示。从最重要的位开始。确定MSB是否为1可以通过布尔运算与适当的数字相乘来完成。如果百万个数字中有超过100个1,就去掉其他带0的数字。现在剩下的数从下一个最有效的位开始。计算排除后剩余数字的数量,只要这个数字大于100,就继续进行。

主要的布尔运算可以在图形处理器上并行完成

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

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

我对此的直接反应是使用堆,但有一种方法可以使用QuickSelect,而不需要在任何时候保留所有的输入值。

创建一个大小为200的数组,并用前200个输入值填充它。运行QuickSelect并丢弃低100个位置,留下100个空闲位置。读入接下来的100个输入值并再次运行QuickSelect。继续执行,直到以100个批次为单位运行整个输入。

最后是前100个值。对于N个值,您运行QuickSelect大约N/100次。每个快速选择的代价大约是某个常数的200倍,所以总代价是某个常数的2N倍。在我看来,输入的大小是线性的,不管我在这个解释中硬连接的参数大小是100。