最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。

我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。

Arrays.sort(array);

面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?


当前回答

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

其他回答

这是谷歌或其他行业巨头提出的问题。也许下面的代码就是面试官想要的正确答案。 时间成本和空间成本取决于输入数组中的最大数量。对于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;
                        }
                    }
                }
            }
        }
    }
}

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

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

            }

        }

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

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

最后是前100个值。对于N个值,您运行QuickSelect大约N/100次。每个快速选择的代价大约是某个常数的200倍,所以总代价是某个常数的2N倍。在我看来,输入的大小是线性的,不管我在这个解释中硬连接的参数大小是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个字节会有性能问题,但这只是为了举例。好的一面是,只需要很少的内存。

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

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