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

Question

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

1.时间复杂度：

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

2.空间复杂度：

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

我在这里有哪些选择？

Answer 1

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

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