algorithm - 以最有效的方式在数组中查找第二个最大值

Question

我试图在空间和时间复杂度方面以最有效的方式找到数组中的第二个最大值，但我有两个主要问题：

1.时间复杂度：

天真的或蛮力方法将需要两次通过才能找到最小的元素，因此复杂度为 O(n)，如果我对数组进行排序，则需要 O(n ² )。

2. 空间复杂度：

我总是可以使用 BST 进行 O(log(n)) 排序，但它们需要额外的空间来维护一棵树，我还可以创建一个堆并执行两次删除，我会得到第二大元素，但这里也创建了堆并且存储在内存中。

我在这里有什么选择？

Answer 1

您可以一次性完成此操作。只需保留两个变量，最大值和第二个最大值。每次更新最大值时，旧的最大值都会变成新的第二个最大值。

这推广到 Top-k 算法，您可以k使用一次通过和 O(k) 空间找到最大（或最小）的元素。在你的情况下k=2。

Answer 2

在列表中找到第 n 个最大的项目称为选择问题，有很多算法可以解决它。http://en.wikipedia.org/wiki/Selection_algorithm

您可以实现的 lis 最低复杂度是 O(n)，因为您需要至少查看列表中的每个项目一次。例如，使用部分插入排序（遍历列表并跟踪前 k 个元素）可以在 O(kn) 时间内从 n 个列表中找到前 k 个项目。

有一种称为 quickselect 的算法可以在 O(n) 时间内找到前 k 个项目，与 k 无关。我建议查找它，但要找到前 2 个，扫描列表一次的简单方法就足够了。