我试图以最有效的方式在空间和时间复杂度方面找到数组中的第二个最大值，但是我有两个主要问题：
天真的或蛮力的方法将需要两次通过才能找到最小的元素，因此O（n）的复杂性。如果我对数组进行排序，则它将花费O（n 2）。
我总是可以使用BST进行O（log（n））排序，但是它们将需要额外的空间来维护树，我还可以创建一个堆并执行两次删除操作，我将获得第二个最大的元素，但是在此还创建了堆并存储在内存中。
我在这里有什么选择？
您可以一口气完成此操作。只需保留两个变量，即最大和第二个最大。每次更新最大值时，旧的最大值都会变成新的第二个最大值。
这可以归结为Top-k算法，您可以在其中k使用一遍和O（k）空间找到最大（或最小）的元素。就你而言k=2。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句