最近我参加了一个面试，面试官要求我“编写一个程序，从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案，即以O(nlogn)时间复杂度对数组进行排序，并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度，我尝试了几个其他的解决方案，但都没有回答他。有没有更好的时间复杂度解决方案?
当前回答
此代码用于在未排序数组中查找N个最大的数字。
#include <iostream>
using namespace std;
#define Array_Size 5 // No Of Largest Numbers To Find
#define BILLION 10000000000
void findLargest(int max[], int array[]);
int checkDup(int temp, int max[]);
int main() {
int array[BILLION] // contains data
int i=0, temp;
int max[Array_Size];
findLargest(max,array);
cout<< "The "<< Array_Size<< " largest numbers in the array are: \n";
for(i=0; i< Array_Size; i++)
cout<< max[i] << endl;
return 0;
}
void findLargest(int max[], int array[])
{
int i,temp,res;
for(int k=0; k< Array_Size; k++)
{
i=0;
while(i < BILLION)
{
for(int j=0; j< Array_Size ; j++)
{
temp = array[i];
res= checkDup(temp,max);
if(res == 0 && max[j] < temp)
max[j] = temp;
}
i++;
}
}
}
int checkDup(int temp, int max[])
{
for(int i=0; i<N_O_L_N_T_F; i++)
{
if(max[i] == temp)
return -1;
}
return 0;
}
这可能不是一个有效的方法，但可以完成工作。
希望这能有所帮助
其他回答
一个非常简单的解决方案是遍历该数组100次。也就是O(n)
每次取出最大的数字(并将其值更改为最小值，以便在下一个迭代中看不到它，或者跟踪以前答案的索引(通过跟踪索引，原始数组可以有多个相同的数字))。经过100次迭代，就得到了最大的100个数字。
Time ~ O(100 * N)
Space ~ O(100 + N)
创建一个包含100个空槽的空列表 对于输入列表中的每个数字: 如果数字小于第一个，跳过 否则用这个数字代替它 然后，将数字通过相邻的交换;直到它比下一个小 返回列表
注意:如果log(input-list.size) + c < 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个字节会有性能问题，但这只是为了举例。好的一面是，只需要很少的内存。
另一个O(n)算法-
该算法通过消元法找到最大的100个
考虑所有的百万数字的二进制表示。从最重要的位开始。确定MSB是否为1可以通过布尔运算与适当的数字相乘来完成。如果百万个数字中有超过100个1，就去掉其他带0的数字。现在剩下的数从下一个最有效的位开始。计算排除后剩余数字的数量，只要这个数字大于100，就继续进行。
主要的布尔运算可以在图形处理器上并行完成
求n个元素中最大的m个元素，其中n >>> m
最简单的解决方案，每个人都应该很明显，就是简单地做m次冒泡排序算法。
然后打印出数组的最后n个元素。
它不需要外部数据结构，并且使用了一种大家都知道的算法。
运行时间估计为O(m*n)。到目前为止最好的答案是O(nlog (m))，所以这个解决方案对于小m来说并不显着昂贵。
我并不是说这不能改进，但这是迄今为止最简单的解决方案。
