最近我参加了一个面试，面试官要求我“编写一个程序，从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案，即以O(nlogn)时间复杂度对数组进行排序，并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度，我尝试了几个其他的解决方案，但都没有回答他。有没有更好的时间复杂度解决方案?
当前回答
这个问题只需一行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(标准库)对于这类问题非常方便。
注意:我并不是说这是最佳的解决方案，但它可以挽救你的面试。
其他回答
这个问题只需一行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(标准库)对于这类问题非常方便。
注意:我并不是说这是最佳的解决方案，但它可以挽救你的面试。
您可以使用快速选择算法在(按顺序)索引[十亿-101]处查找数字 然后遍历这些数字找出比这个数字更大的数。
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建议的第二个选择是:
使用堆构建最大堆将花费O(N)，然后前100个最大的数字将在堆的顶部，所有你需要的是把它们从堆(100 X O(Log(N))。
该算法时间为:O(N) + 100 X O(Log(N)) = O(N)
此代码用于在未排序数组中查找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;
}
这可能不是一个有效的方法，但可以完成工作。
希望这能有所帮助
两个选择:
(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)映射-约简模型。
这与hadoop中的单词计数示例非常相似。 映射工作:计算每个元素出现的频率或次数。 减约:获取顶部K元素。
通常，我会给招聘人员两个答案。他们喜欢什么就给什么。当然，映射缩减编码会很费事，因为您必须知道每个确切的参数。练习一下也无妨。 祝你好运。
取十亿个数字中的前一百个，然后排序。现在只需遍历十亿，如果源数大于100中最小的数，则按排序顺序插入。你得到的结果更接近于O(n)除以集合的大小。
