问面试算法:在n个大小的数组中找到两个最大元素

EN

递归地拆分数组，在每一半中找到最大的元素，然后找到最大的元素，这是比较过的最大的元素。第一部分要求n比较，最后一部分要求O(log )。下面是一个示例：

1 2 5 4 9 7 8 7 5 4 1 0 1 4 2 3
2   5   9   8   5   1   4   3
5       9       5       4
9               5
9

在每一步，我合并相邻的数字，并采取较大的两个。用n比较得到最大的数，9。然后，如果我们看每一个与(5，5，8，7)相比较的数字，我们就会发现最大的一个是8，这肯定是数组中的第二大。由于其中有O(log )级别，因此需要进行O(log )比较。

对于只有2最大元素，正常选择可能足够好。基本上是O(2*n)。

对于更一般的“从数组大小n中选择k元素”的问题，快速排序是一个很好的想法，但您不必真正对整个数组进行排序。

尝尝这个

1. 选择一个枢轴，将数组拆分为Nm和Nm，如果k< m，则忽略Nm部分，在Nm中执行步骤1。如果k> m，则执行
2. ，忘记Nm部分，在Nn-m中执行步骤1。这一次，您试图在Nn-m.
3. 中找到第一个k-m元素，如果k= m，就得到了。

。

这基本上就像在数组N中定位k一样，您需要log(N)迭代，并平均移动(N/2)^i元素。因此，它是一个N+ log(N)算法(满足您的要求)，并且具有非常好的实际性能(比普通的快速排序更快，因为它避免了任何排序，因此输出没有排序)。