编写一个程序，从10亿个数字的数组中找到最大的100个数字。

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

伪代码：

//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)。

这个算法的快速解释如下： 本质上，该系统试图利用2D数组中每个数字的索引和数字的值，并将它们作为索引来跟踪已插入到数组中的该值数字的数量。当达到100时，它会关闭所有“低级分支”。

该算法的时间大约为O(十亿*log(16)*7)+O(100)。我可能错了。此外，很可能需要调试，因为它有点复杂，我只是凭空写的。

编辑：没有解释的负评并不有益。如果您认为这个答案是错误的，请留下评论告诉我原因。 StackOverflow甚至在你给出负评时也会告诉你这么做。

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

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

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

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

   • 否则，用该数字替换它

   • 然后通过相邻交换将该数字推进，直到它小于下一个数字

3. 返回该列表

---

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

这是来自谷歌或其他行业巨头的问题。也许以下代码是你的面试官期望的正确答案。 时间成本和空间成本取决于输入数组中的最大数字。对于32位整数数组输入，最大空间成本为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;
                        }
                    }
                }
            }
        }
    }
}

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

重复这个过程，每次从堆中挑选100个元素并添加900个来自文件的元素。

最后挑选100个元素将给我们一个十亿个数字中的最大的100个元素。

另一个O(n)算法 -

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

考虑它们的二进制表示中的所有一百万个数字。从最高有效位开始。可以通过与适当数字相乘的布尔运算来找到MSB是否为1。如果这一百万个数字中有100个以上的1，则用0消除其他数字。现在，对于剩余数字，请继续处理下一个最高有效位。在消除后保持剩余数字数量的计数，并在此数字大于100时继续进行。

主要布尔操作可以并行在GPU上完成

我会找出谁有时间把十亿个数字放进一个数组里并解雇他。一定是政府工作人员。如果你有一个链表，至少可以在中间插入一个数字而不必移动五亿个数字来腾出空间。更好的方法是使用B树进行二分查找。每次比较都可以消除一半的总数。哈希算法可以像棋盘一样填充数据结构，但对于稀疏数据效果不佳。因此，最好的方法是使用一个100个整数的解决方案数组，并跟踪解决方案数组中的最小数字，这样当您遇到原始数组中的更高数字时就可以替换它。假设原始数组未排序，则必须查看原始数组中的每个元素。

管理一个单独的列表需要额外的工作，每次找到另一个替换项时都必须移动整个列表中的内容。只需使用qsort对其进行排序并选择前100个即可。

1. 使用nth-element获取第100个元素O(n)
2. 第二次迭代，但仅一次，并输出每个大于此特定元素的元素。

请注意，特别是第二步可能很容易并行计算！当您需要一百万个最大元素时，它也将非常高效。

可能的改进。

如果文件包含10亿个数字，读取它可能需要非常长的时间...

为了改善这个工作，您可以：

• 将文件分成n个部分，创建n个线程，使每个线程查找文件中其部分的100个最大数字（使用优先队列），最后获取所有线程输出的100个最大数字。
• 使用类似hadoop的解决方案在集群上执行此任务。在这里，您可以将文件分割得更细，并且对于包含10亿（或10^12）个数字的文件，可以更快地获得输出。

复杂度为O(N)

首先创建一个包含100个整数的数组，将该数组的第一个元素初始化为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)

} 

完成后，以模100的方式从CurrentBig打印M数组100次 :-) 对于学生：确保代码的最后一行不会在代码退出前覆盖有效数据