一个经典的面试问题:如何从N个数中选择最大(最小)的N个数？

这个问题我想了快一年了，也和很多人讨论过。根据我得到的信息，谷歌和微软都面临过这个问题。可能很多人听说过这个问题或者知道答案(所谓堆)，但是我想把我的答案写出来。我的分析可能有漏洞，出于交流的目的。但这是个复杂的问题，挺有意思的。看完这篇文章，你可能会受到一些意想不到的解决方案的启发(我一直认为heap不一定是最高效的算法)。在本文中，我们将始终以寻找n个最大数作为统一的分析实例。注:这篇文章会写得详细一些，让大部分人都能看懂，不要介意我的啰嗦:)我不确定有多少人有耐心看完这篇文章！朴素方法:首先我们假设N和N都可以容纳在内存中，即N的个数可以一次性装入内存并存放在数组中(如果需要链表估计，又是一个具有挑战性的问题)。从最简单的情况出发，如果n=1，那么毫无疑问。必须比较N-1次才能得到最大的数，直接遍历N个数就行了。如果n=2呢？当然也可以直接遍历N数组两次，第一遍得到最大数max1。但是当你遍历第二遍寻找第二大的数max2时，每次都要判断取N的元素下标不等于max1的下标，这样会大大增加比较的次数。这个问题是有解决办法的。我们可以把N数组以max1为分界点分成两部分，然后遍历这两部分得到两个最大数，然后选择其中一个得到max2。你也可以通过遍历一次来解决这个问题。首先维护两个元素，max1和max2(max1=max2)。从n得到一个数后，先和max1比较。如果大于max1(必须大于max2)，直接替换max1，否则。以类似的方式，可以对n=2、3和4进行同样的操作。该算法的时间复杂度为O(nN)。当N越来越大时(不能超过N/2，否则就变成了求N-n个最小数的对偶问题)，这种算法的效率就会越来越差。但是当n比较小时(很难说有多小)，这个算法的实际效率应该是很好的，因为它比较简单，没有递归调用等系统损耗。heap:n大的时候应该用什么算法？首先，我们分析上面的算法。当从N中取出一个新数M时，需要依次与max1，max2，max3max n进行比较，直到找到一个小于M的max x，再用M代替，平均比较次数为n/2。可以用比较少的来代替吗？最直观的方法就是，也就是网上文章推崇的堆。堆有一些优点:1。它是一棵完整的二叉树，树的深度是同一个节点的二叉树中最少的，所以维护效率高；2.可以用数组来实现，父节点P与左右子节L和R的数组下标的关系为s[l] = 2*s[p]+1，s[r] = 2*s[p]+2。在计算机中，2*s[p]的运算可以通过左移1位来实现，效率非常高。另外数组可以随机访问，效率也很高。3.堆的提取操作，即移除堆顶并重新维护堆的时间复杂度为O(logn)，其中n是堆的大小。具体到我们的问题，如何实现？首先打开一个大小为N的数组区域A，然后从N中读取N个数填充到A中，然后将A维护为一个小的顶堆(即A中最小的数存放在顶堆A[0])中。然后从N中取出下一个数，也就是n+1的数M，将M与堆顶A[0]进行比较。如果M