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

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

Arrays.sort(array);

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


当前回答

我意识到这被标记为“算法”,但会抛出一些其他选项,因为它可能也应该被标记为“面试”。

10亿个数字的来源是什么?如果它是一个数据库,那么“从表中按值顺序选择值desc limit 100”就可以很好地完成工作-可能有方言差异。

这是一次性的,还是会重复发生?如果重复,频率是多少?如果它是一次性的,数据在一个文件中,那么'cat srcfile | sort(根据需要选择)| head -100'将让你快速完成有偿工作,而计算机处理这些琐碎的琐事。

如果重复,你会建议选择任何合适的方法来获得初始答案并存储/缓存结果,这样你就可以连续地报告前100名。

Finally, there is this consideration. Are you looking for an entry level job and interviewing with a geeky manager or future co-worker? If so, then you can toss out all manner of approaches describing the relative technical pros and cons. If you are looking for a more managerial job, then approach it like a manager would, concerned with the development and maintenance costs of the solution, and say "thank you very much" and leave if that is the interviewer wants to focus on CS trivia. He and you would be unlikely to have much advancement potential there.

祝你下次面试好运。

其他回答

可能的改进。

如果文件包含十亿的数字,读取它可能会很长…

为了提高工作效率,你可以:

将文件分成n个部分,创建n个线程,让n个线程在各自的部分中寻找最大的100个数字(使用优先级队列),最后得到所有线程输出的最大的100个数字。 使用像hadoop这样的解决方案,使用集群来完成这样的任务。在这里,您可以进一步分割文件,并更快地输出10亿(或10^12)个数字的文件。

此代码用于在未排序数组中查找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;
}

这可能不是一个有效的方法,但可以完成工作。

希望这能有所帮助

求n个元素中最大的m个元素,其中n >>> m

最简单的解决方案,每个人都应该很明显,就是简单地做m次冒泡排序算法。

然后打印出数组的最后n个元素。

它不需要外部数据结构,并且使用了一种大家都知道的算法。

运行时间估计为O(m*n)。到目前为止最好的答案是O(nlog (m)),所以这个解决方案对于小m来说并不显着昂贵。

我并不是说这不能改进,但这是迄今为止最简单的解决方案。

简单的解决方案是使用优先队列,将前100个数字添加到队列中,并跟踪队列中最小的数字,然后遍历其他10亿个数字,每当我们发现一个比优先队列中最大的数字大的数字时,我们删除最小的数字,添加新的数字,并再次跟踪队列中最小的数字。

如果这些数字是随机顺序的,这就很好了,因为当我们迭代10亿个随机数字时,下一个数字是目前为止最大的100个数字之一的情况是非常罕见的。但这些数字可能不是随机的。如果数组已经按升序排序,则始终向优先队列插入一个元素。

我们先从数组中选取100,000个随机数。为了避免可能很慢的随机访问,我们添加了400个随机组,每个组有250个连续的数字。通过这种随机选择,我们可以非常确定,剩下的数字中很少有进入前100位的,因此执行时间将非常接近于一个简单的循环,将10亿个数字与某个最大值进行比较。

另一个O(n)算法-

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

考虑所有的百万数字的二进制表示。从最重要的位开始。确定MSB是否为1可以通过布尔运算与适当的数字相乘来完成。如果百万个数字中有超过100个1,就去掉其他带0的数字。现在剩下的数从下一个最有效的位开始。计算排除后剩余数字的数量,只要这个数字大于100,就继续进行。

主要的布尔运算可以在图形处理器上并行完成