编写一个程序，从一个包含10亿个数字的数组中找出100个最大的数字

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

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

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

你可以保留一个最大的100个数字的优先队列，遍历10亿个数字。每当遇到大于队列中最小数字(队列头)的数字时，删除队列头并将新数字添加到队列中。

用一堆实现的优先级队列的插入+删除复杂度为O(log K)。(其中K = 100，要查找的元素数量。N = 10亿，数组中元素的总数)。

在最坏的情况下，对于O(N log N)基于比较的排序__abc2，你会得到billion*log2(100)，这比billion*log2(billion)要好。

一般来说，如果你需要N个数字中最大的K个数字，复杂度是O(N log K)而不是O(N log N)，当K与N相比非常小时，这可能非常重要。

这种优先级队列算法的预期时间非常有趣，因为在每次迭代中可能会出现插入，也可能不会出现插入。

第i个数字被插入队列的概率是一个随机变量大于同一分布中至少i-K个随机变量的概率(前k个数字自动添加到队列中)。我们可以使用顺序统计(参见链接)来计算这个概率。

例如，假设这些数字是从{0, 1}中随机选择的统一，第(i- k)个数字(从i个数字中)的期望值是(i-k)/i，随机变量大于此值的概率是1-[(i-k)/i] = k/i。

因此，期望插入数为:

期望运行时间可表示为:

(k时间来生成包含第一个k元素的队列，然后是n-k比较，以及如上所述的预期插入次数，每次插入的平均时间为log(k)/2)

注意，当N相对于K非常大时，这个表达式更接近n而不是N log K。这有点直观，因为在这个问题中，即使经过10,000次迭代(与十亿次相比非常小)，将数字插入队列的机会也非常小。

它们可能倾向于增加，在这种情况下，大多数或所有数字将成为所见最大的100个数字集合的新候选数。该算法的最坏情况是O(N log K)。

或者如果它们趋于减少，最大的100个数字中的大多数将非常早，并且我们的最佳情况下运行时间本质上是O(N + K log K)，它只是O(N)对于K比N小得多。

脚注1:O(N)整数排序/直方图

计数排序或基数排序都是O(N)，但通常有更大的常数因子，使它们在实践中比比较排序更差。在一些特殊情况下，它们实际上相当快，主要用于窄整数类型。

例如，如果数字很小，计数排序表现良好。16位数字只需要2^16个计数器的数组。而不是实际展开到一个排序的数组，你可以扫描你建立的直方图作为计数排序的一部分。

在对数组进行直方图化之后，您可以快速回答任何顺序统计的查询，例如最大的99个数字，最大的200到100个数字)32位数字将计数分散到一个更大的数组或计数器哈希表中，可能需要16gib的内存(每个2^32个计数器4字节)。在真正的cpu上，可能会有很多TLB和缓存失误，不像2^16个元素的数组，L2缓存通常会命中。

类似地，Radix Sort可以在第一次传递后只查看顶部的桶。但是常数因子仍然可能大于log K，这取决于K。

注意，每个计数器的大小足够大，即使所有N个整数都是重复的，也不会溢出。10亿略小于2^30，所以一个30位无符号计数器就足够了。32位有符号或无符号整数就可以了。

如果有更多的计数器，则可能需要64位计数器，初始化为零并随机访问需要占用两倍的内存。或者是少数溢出16或32位整数的计数器的哨兵值，以指示计数的其余部分在其他地方(在一个小字典中，例如映射到64位计数器的哈希表中)。

取十亿个数字中的前一百个，然后排序。现在只需遍历十亿，如果源数大于100中最小的数，则按排序顺序插入。你得到的结果更接近于O(n)除以集合的大小。

array={...the billion numbers...}
result[100];


pivot=QuickSelect(array,billion-101);//O(N)


for(i=0;i<billion;i++)//O(N)
if(array[i]>=pivot)
result.add(array[i]);

该算法时间为:2 X O(N) = O(N)(平均情况性能)

像Thomas Jungblut这样的第二个选项建议:

使用堆构建MAX堆将占用O(N)，然后前100个MAX数将位于堆的顶部，所有你需要做的就是将它们从堆中取出(100 X O(Log(N))。

该算法时间为:O(N) + 100 X O(Log(N)) = O(N)

虽然其他的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的包含随机索引的新数组。

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

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

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

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

我用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个值，而不进行任何排序，并记住这个缓冲区的最小值。首先，我认为这个方法是由fordprefect提出的，但在评论中他说他假设100位数据结构被实现为堆。每当发现一个大于该值的新数字时，缓冲区中的最小值将被新发现的值覆盖，并再次在缓冲区中搜索当前最小值。如果十亿数字数组中的数字是随机分布的，则大数组中的值将与小数组中的最小值进行比较而被丢弃。只有对于一个非常非常小的数字的一部分，值必须插入到小数组。因此，对持有小数字的数据结构进行操作的差异可以忽略不计。对于少数元素，很难确定使用优先队列是否比使用我的简单方法更快。

• 在理论层面:在堆中插入需要多少比较。我知道它是O(log(n))但常数因子有多大呢?我

• 在机器级别:缓存和分支预测对堆插入和数组中线性搜索的执行时间有什么影响?

• 在实现级别:库或编译器提供的堆数据结构中隐藏了哪些额外成本?

我认为，在人们试图估计100个元素堆和100个元素数组的性能之间的真正区别之前，这些都是必须回答的一些问题。所以做一个实验并测量真实的表现是有意义的。

求n个元素中最大的m个元素，其中n >>> m

最简单的解决方案，每个人都应该很明显，就是简单地做m次冒泡排序算法。

然后打印出数组的最后n个元素。

它不需要外部数据结构，并且使用了一种大家都知道的算法。

运行时间估计为O(m*n)。到目前为止最好的答案是O(nlog (m))，所以这个解决方案对于小m来说并不显着昂贵。

我并不是说这不能改进，但这是迄今为止最简单的解决方案。

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

他的描述很笼统，所以也许你可以问他这些数字的范围或意义，让问题更清楚。这样做可能会给面试官留下深刻印象。例如，如果这些数字代表人们的年龄，那么这个问题就简单多了。合理地假设活着的人年龄都不超过200岁，您可以使用一个大小为200(可能是201)的整数数组在一次迭代中计算相同年龄的人数。这里的指数表示年龄。在这之后，找到100个最大的数就是小菜一碟了。顺便说一下，这个算法叫做< >强计数排序< / >强。

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

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

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

然而!查看列表填充机制是否以特定顺序填充该列表。它们是否在一个定义良好的模式中，你可以肯定地知道最大的数字将在列表的某个区域或某个间隔内找到?这可能是有规律的。如果是这样的话,例如如果他们保证在正态分布的一些特征峰在中间,总是重复上升趋势中定义的子集,有长期上涨一段时间T的数据集可能发生的内幕交易或设备故障,或者只是有一个“飙升”每n个数在一场灾难后力的分析,可以减少你必须检查的记录数量。

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

我意识到这被标记为“算法”，但会抛出一些其他选项，因为它可能也应该被标记为“面试”。

10亿个数字的来源是什么?如果它是一个数据库，那么“从表中按值顺序选择值desc limit 100”就可以很好地完成工作-可能有方言差异。

这是一次性的，还是会重复发生?如果重复，频率是多少?如果它是一次性的，数据在一个文件中，那么'cat srcfile | sort(根据需要选择)| head -100'将让你快速完成有偿工作，而计算机处理这些琐碎的琐事。

如果重复，你会建议选择任何合适的方法来获得初始答案并存储/缓存结果，这样你就可以连续地报告前100名。

最后，还有这样的考虑。你是否正在寻找一份入门级的工作，并与一个极客的经理或未来的同事进行面试?如果是这样的话，那么你可以抛开所有描述相关技术优缺点的方法。如果你正在寻找一份更具管理性的工作，那么就像一个经理一样，关注解决方案的开发和维护成本，并说“非常感谢”，如果面试官想关注CS琐事，你就离开。他和你在那里都不太可能有太大的晋升潜力。

祝你下次面试好运。

我知道这可能会被埋没，但这是我对radix MSD的一个变体的想法。

pseudo-code:

//billion is the array of 1 billion numbers
int[] billion = getMyBillionNumbers();
//this assumes these are 32-bit integers and we are using hex digits
int[][] mynums = int[8][16];


for number in billion
putInTop100Array(number)


function putInTop100Array(number){
//basically if we got past all the digits successfully
if(number == null)
return true;
msdIdx = getMsdIdx(number);
msd = getMsd(number);
//check if the idx above where we are is already full
if(mynums[msdIdx][msd+1] > 99) {
return false;
} else if(putInTop100Array(removeMSD(number)){
mynums[msdIdx][msd]++;
//we've found 100 digits here, no need to keep looking below where we are
if(mynums[msdIdx][msd] > 99){
for(int i = 0; i < mds; i++){
//making it 101 just so we can tell the difference
//between numbers where we actually found 101, and
//where we just set it
mynums[msdIdx][i] = 101;
}
}
return true;
}
return false;
}

函数getMsdIdx(int num)将返回最高位(非零)的下标。函数getMsd(int num)将返回最高位。函数removeMSD(int num)将从一个数字中删除最高有效位数并返回该数字(如果删除最高有效位数后没有剩余，则返回null)。

一旦完成，剩下的就是遍历mynums以获取前100位数字。这大概是这样的:

int[] nums = int[100];
int idx = 0;
for(int i = 7; i >= 0; i--){
int timesAdded = 0;
for(int j = 16; j >=0 && timesAdded < 100; j--){
for(int k = mynums[i][j]; k > 0; k--){
nums[idx] += j;
timesAdded++;
idx++;
}
}
}

我要注意的是，尽管上面的函数看起来时间复杂度很高，但实际上它只会在O(7*100)左右。

这个算法的时间类似于O(billion*log(16)*7)+O(100)。我可能是错的。此外，这很可能需要调试，因为它有点复杂，我只是把它写在我的头上。

编辑:没有解释的反对票是没有帮助的。如果你认为这个答案不正确，请留下评论。我很确定，StackOverflow甚至告诉你这样做，当你向下投票。

两个选择:

(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)映射-约简模型。

受@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的i3核心)上，它需要25秒，并进行1724次排序。 我用dd if=/dev/urandom/ count=1000000000 bs=1为这次运行生成了一个二进制文件

显然，一次只从磁盘读取4个字节会有性能问题，但这只是为了举例。好的一面是，只需要很少的内存。

Time ~ O(100 * N)
Space ~ O(100 + N)

1. 创建一个包含100个空槽的空列表

2. 对于输入列表中的每个数字:

   • 如果数字小于第一个，跳过

   • 否则用这个数字代替它

   • 然后，将数字通过相邻的交换;直到它比下一个小

   李< / ul > < / >

   • 返回列表

注意:如果为log(input-list.size) + c < 100，则最佳方法是对输入列表进行排序，然后拆分前100项。

复杂度为O(N)

遍历N个值

if N[i] > M[CurrentBig] {


M[CurrentBig]=N[i]; ( overwrite the current value with the newly found larger number)


CurrentBig++;      ( go to the next position in the M array)


CurrentBig %= 100; ( modulo arithmetic saves you from using lists/hashes etc.)


M[CurrentBig]=N[i];    ( pick up the current value again to use it for the next Iteration of the N array)


}

当完成时，从CurrentBig中打印M数组100次模100:-) 对于学生:确保代码的最后一行没有在代码退出

另一个O(n)算法-

该算法通过消元法找到最大的100个

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

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

我会找出谁有时间把十亿个数字放进一个数组，然后炒了他。必须为政府工作。至少如果你有一个链表，你可以在中间插入一个数字，而不用移动5亿来腾出空间。更好的是，b树允许二分搜索。每次比较都会减少总数的一半。哈希算法允许您像棋盘一样填充数据结构，但不太适合稀疏数据。因为你最好的办法是有一个100个整数的解数组，并跟踪你的解数组中最小的数字，这样当你在原始数组中遇到一个更高的数字时，你就可以替换它。你必须查看原始数组中的每一个元素假设它一开始就没有排序。

此代码用于查找< em > < / em >未排序的数组中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;
}

这可能不是一个有效的方法，但可以完成工作。

希望这能有所帮助

你可以在O(n)时间内完成。只需遍历列表，并跟踪在任何给定点上看到的最大的100个数字，以及该组中的最小值。当你发现一个新的数字大于你的10个数字中的最小值，然后替换它并更新你的新的100的最小值(可能每次你都要花100的常数时间来确定，但这并不影响整体分析)。

一个非常简单的解决方案是遍历该数组100次。它是O(n)。

每次取出最大的数字(并将其值更改为最小值，以便在下一个迭代中看不到它，或者跟踪以前答案的索引(通过跟踪索引，原始数组可以有多个相同的数字))。经过100次迭代，就得到了最大的100个数字。

管理一个单独的列表是额外的工作，每次你找到另一个替代物时，你都必须在整个列表中移动东西。把它排序，选前100名。

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

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

public class TopNumber {
public static void main(String[] args) {
final int input[] = {2389,8922,3382,6982,5231,8934
,4322,7922,6892,5224,4829,3829
,6892,6872,4682,6723,8923,3492};
//One int(4 bytes) hold 32 = 2^5 value,
//About 4 * 125M Bytes
//int sort[] = new int[1 << (32 - 5)];
//Allocate small array for local test
int sort[] = new int[1000];
//Set all bit to 0
for(int index = 0; index < sort.length; index++){
sort[index] = 0;
}
for(int number : input){
sort[number >>> 5] |= (1 << (number % 32));
}
int topNum = 0;
outer:
for(int index = sort.length - 1; index >= 0; index--){
if(0 != sort[index]){
for(int bit = 31; bit >= 0; bit--){
if(0 != (sort[index] & (1 << bit))){
System.out.println((index << 5) + bit);
topNum++;
if(topNum >= 3){
break outer;
}
}
}
}
}
}
}

最近我采用了一种理论，认为世界上所有的问题都可以用O(1)来解决。甚至是这个。从这个问题中不清楚这些数字的范围是什么。如果数字的范围在1到10之间，那么前100个最大的数字可能是10个。从10亿个数字中选出最大值的概率是非常大的当最大值相对于10亿个数字来说非常小的时候。所以我会在面试中给出这个答案。

 Although in this question we should search for top 100 numbers, I will
generalize things and write x. Still, I will treat x as constant value.

n中最大的x元素: < / >强

调用返回值列表。它是一个x元素的集合(在我看来应该是链表)

• 第一个x元素从池中取出，并在LIST中排序(这在常数时间内完成，因为x被视为常数- O(x log(x))时间)
• 对于接下来的每个元素，我们检查它是否比LIST中最小的元素大，如果是，我们就弹出最小的元素并将当前元素插入LIST中。因为这是一个有序列表，每个元素都应该在对数时间内找到它的位置(二进制搜索)，而且因为它是有序列表，插入不是一个问题。每一步也是在常数时间内完成(O(log(x))时间)。

那么，最坏的情况是什么?

xlog (X)+ (n- X)(log(X)+1) = nlog(X)+ n- X

最坏情况是O(n)时间。+1是检查数字是否大于LIST中最小的数字。平均情况的预期时间将取决于这n个元素的数学分布。

< >强可能的改进 < / >强

在最坏的情况下，这个算法可以稍微改进，但恕我直言(我无法证明这一点)，这会降低平均行为。渐近行为是一样的。

该算法的改进在于，我们将不检查元素是否大于最小值。对于每个元素，我们将尝试插入它，如果它小于最小值，我们将忽略它。尽管如果我们只考虑我们将面临的最坏的情况，这听起来很荒谬

X log(X) + (n-x)log(X) = nlog(X)

操作。

对于这个用例，我没有看到任何进一步的改进。但是你必须问自己，如果我要对不同的x做多于log(n)次呢?显然，我们会以O(nlog (n))为单位对数组进行排序，并在需要时提取x元素。

这个问题只需一行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(标准库)对于这类问题非常方便。

注意:我并不是说这是最佳的解决方案，但它可以挽救你的面试。

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

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]);


}


}

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

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

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

可能的改进。

如果文件包含十亿的数字，读取它可能是真的 long…

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

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

从十亿个数字中找出前100个最好使用包含100个元素的最小堆。

首先用遇到的前100个数字对最小堆进行质数。Min-heap将前100个数字中最小的存储在根(顶部)。

现在，当你继续计算其他数字时，只将它们与根数(100中最小的数)进行比较。

如果遇到的新数字大于最小堆的根，则将根替换为该数字，否则忽略它。

作为在最小堆中插入新数字的一部分，堆中最小的数字将移到顶部(根)。

一旦我们遍历了所有的数字，我们将得到最小堆中最大的100个数字。

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

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

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