最近我参加了一个面试，面试官要求我“编写一个程序，从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案，即以O(nlogn)时间复杂度对数组进行排序，并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度，我尝试了几个其他的解决方案，但都没有回答他。有没有更好的时间复杂度解决方案?
当前回答
另一个O(n)算法-
该算法通过消元法找到最大的100个
考虑所有的百万数字的二进制表示。从最重要的位开始。确定MSB是否为1可以通过布尔运算与适当的数字相乘来完成。如果百万个数字中有超过100个1，就去掉其他带0的数字。现在剩下的数从下一个最有效的位开始。计算排除后剩余数字的数量，只要这个数字大于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的循环队列中。
循环队列的最小值就是新的比较值。继续往队列中添加。如果已满，则从队列中提取最小值。
这是谷歌或其他行业巨头提出的问题。也许下面的代码就是面试官想要的正确答案。 时间成本和空间成本取决于输入数组中的最大数量。对于32位int数组输入，最大空间成本是4 * 125M字节，时间成本是5 *十亿。
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(n)算法-
该算法通过消元法找到最大的100个
考虑所有的百万数字的二进制表示。从最重要的位开始。确定MSB是否为1可以通过布尔运算与适当的数字相乘来完成。如果百万个数字中有超过100个1，就去掉其他带0的数字。现在剩下的数从下一个最有效的位开始。计算排除后剩余数字的数量，只要这个数字大于100，就继续进行。
主要的布尔运算可以在图形处理器上并行完成
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元素:
我将调用返回值LIST。它是一个x元素的集合(在我看来应该是链表)
First x elements are taken from pool "as they come" and sorted in LIST (this is done in constant time since x is treated as constant - O( x log(x) ) time) For every element that comes next we check if it is bigger than smallest element in LIST and if is we pop out the smallest and insert current element to LIST. Since that is ordered list every element should find its place in logarithmic time (binary search) and since it is ordered list insertion is not a problem. Every step is also done in constant time ( O(log(x) ) time ).
那么，最坏的情况是什么?
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元素。
