最近我参加了一个面试，面试官要求我“编写一个程序，从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案，即以O(nlogn)时间复杂度对数组进行排序，并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度，我尝试了几个其他的解决方案，但都没有回答他。有没有更好的时间复杂度解决方案?
当前回答
可能的改进。
如果文件包含十亿的数字，读取它可能会很长…
为了提高工作效率，你可以:
将文件分成n个部分，创建n个线程，让n个线程在各自的部分中寻找最大的100个数字(使用优先级队列)，最后得到所有线程输出的最大的100个数字。 使用像hadoop这样的解决方案，使用集群来完成这样的任务。在这里，您可以进一步分割文件，并更快地输出10亿(或10^12)个数字的文件。
其他回答
可能的改进。
如果文件包含十亿的数字，读取它可能会很长…
为了提高工作效率，你可以:
将文件分成n个部分，创建n个线程，让n个线程在各自的部分中寻找最大的100个数字(使用优先级队列)，最后得到所有线程输出的最大的100个数字。 使用像hadoop这样的解决方案，使用集群来完成这样的任务。在这里，您可以进一步分割文件，并更快地输出10亿(或10^12)个数字的文件。
我用Python写了一个简单的解决方案，以防有人感兴趣。它使用bisect模块和一个临时返回列表，它保持排序。这类似于优先级队列实现。
import bisect
def kLargest(A, k):
'''returns list of k largest integers in A'''
ret = []
for i, a in enumerate(A):
# For first k elements, simply construct sorted temp list
# It is treated similarly to a priority queue
if i < k:
bisect.insort(ret, a) # properly inserts a into sorted list ret
# Iterate over rest of array
# Replace and update return array when more optimal element is found
else:
if a > ret[0]:
del ret[0] # pop min element off queue
bisect.insort(ret, a) # properly inserts a into sorted list ret
return ret
使用100,000,000个元素和最坏情况输入是一个排序列表:
>>> from so import kLargest
>>> kLargest(range(100000000), 100)
[99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907,
99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915,
99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923,
99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931,
99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939,
99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947,
99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955,
99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963,
99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971,
99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979,
99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987,
99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995,
99999996, 99999997, 99999998, 99999999]
我花了40秒计算1亿个元素，所以我不敢计算10亿个元素。为了公平起见，我给它提供了最坏情况的输入(具有讽刺意味的是，一个已经排序的数组)。
从十亿个数字中找到前100个最好使用包含100个元素的最小堆。
首先用遇到的前100个数字对最小堆进行质数。Min-heap将前100个数字中最小的存储在根(顶部)。
现在，当你继续计算其他数字时，只将它们与根数(100中最小的数)进行比较。
如果遇到的新数字大于最小堆的根，则将根替换为该数字，否则忽略它。
作为在最小堆中插入新数字的一部分，堆中最小的数字将移到顶部(根)。
一旦我们遍历了所有的数字，我们将得到最小堆中最大的100个数字。
受@ron teller回答的启发，这里有一个简单的C程序来做你想做的事情。
#include <stdlib.h>
#include <stdio.h>
#define TOTAL_NUMBERS 1000000000
#define N_TOP_NUMBERS 100
int
compare_function(const void *first, const void *second)
{
int a = *((int *) first);
int b = *((int *) second);
if (a > b){
return 1;
}
if (a < b){
return -1;
}
return 0;
}
int
main(int argc, char ** argv)
{
if(argc != 2){
printf("please supply a path to a binary file containing 1000000000"
"integers of this machine's wordlength and endianness\n");
exit(1);
}
FILE * f = fopen(argv[1], "r");
if(!f){
exit(1);
}
int top100[N_TOP_NUMBERS] = {0};
int sorts = 0;
for (int i = 0; i < TOTAL_NUMBERS; i++){
int number;
int ok;
ok = fread(&number, sizeof(int), 1, f);
if(!ok){
printf("not enough numbers!\n");
break;
}
if(number > top100[0]){
sorts++;
top100[0] = number;
qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function);
}
}
printf("%d sorts made\n"
"the top 100 integers in %s are:\n",
sorts, argv[1] );
for (int i = 0; i < N_TOP_NUMBERS; i++){
printf("%d\n", top100[i]);
}
fclose(f);
exit(0);
}
在我的机器上(具有快速SSD的core i3)，它需要25秒，并进行1724种排序。 我用dd if=/dev/urandom/ count=1000000000 bs=1生成了一个二进制文件。
显然，一次只从磁盘读取4个字节会有性能问题，但这只是为了举例。好的一面是，只需要很少的内存。
这个问题只需一行c++代码就可以用N log(100)的复杂度(而不是N log N)来回答。
std::vector<int> myvector = ...; // Define your 1 billion numbers.
// Assumed integer just for concreteness
std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());
最终答案将是一个向量，其中前100个元素保证是数组中最大的100个数字，而其余元素是无序的
c++ STL(标准库)对于这类问题非常方便。
注意:我并不是说这是最佳的解决方案，但它可以挽救你的面试。
