algorithm - 面试算法：在大小为 n 的数组中找到两个最大的元素

Question

这是我在网上看到的一个面试问题，我不确定我的想法是否正确。

问题在这里：

设计一个算法，在 n 个数字的序列中找到两个最大的元素。比较次数需要为 n + O(log n)

我想我可能会选择快速排序并在找到两个最大元素时停止？但不能100%确定。任何人有想法请分享

Answer 1

递归拆分数组，在每一半中找到最大的元素，然后找到与最大元素进行比较的最大元素。第一部分需要 n 次比较，最后一部分需要 O(log n)。这是一个例子：

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。然后，如果我们查看将 9 与 (5, 5, 8, 7) 进行比较的每个数字，我们会看到最大的数字是 8，它一定是数组中的第二大。由于其中有 O(log n) 级别，因此需要 O(log n) 比较才能做到这一点。

Answer 2

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

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

试试这个

1. 您选择一个枢轴，将数组拆分为 N[m] 和 N[nm]。
2. 如果 k < m，忘记 N[nm] 部分，执行 N[m] 中的步骤 1。
3. 如果 k > m，忘记 N[m] 部分，进入 N[nm]。这一次，您尝试在 N[nm] 中找到第一个 km 元素。
4. 如果 k = m，你明白了。

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