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

您可以使用快速选择算法在(按顺序)索引[十亿-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)

Recently I am adapting a theory that all the problems in the world could be solved with O(1). And even this one. It wasn't clear from the question what is the range of the numbers. If the numbers are it range from 1 to 10, then probably the the top 100 largest numbers will be a group of 10. The chance that the highest number will be picked out of the 1 billion numbers when the highest number is very small in compare to to 1 billion are very big. So I would give this as an answer in that interview.

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

创建一个包含100个空槽的空列表 对于输入列表中的每个数字: 如果数字小于第一个，跳过 否则用这个数字代替它 然后，将数字通过相邻的交换;直到它比下一个小 返回列表

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

此代码用于在未排序数组中查找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个int的数组，将这个数组的第一个元素初始化为N个值的第一个元素， 用另一个变量CurrentBig来跟踪当前元素的索引

遍历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:-) 对于学生:确保代码的最后一行在代码退出之前没有胜过有效数据