我最近发现在STL中存在一个名为nth_element的方法.引用描述:
Nth_element类似于partial_sort,因为它部分地对一系列元素进行排序:它排列范围[first,last],使得迭代器nth指向的元素与该位置中的元素相同(如果整个范围[第一个,最后一个]已经排序.另外,[nth,last]范围内的元素都不小于[first,nth]范围内的任何元素.
它声称平均具有O(n)复杂性.算法如何工作？我找不到任何解释.
我试图在空间和时间复杂度方面以最有效的方式找到数组中的第二个最大值，但我有两个主要问题：
天真或蛮力方法将需要两次通过才能找到最小元素，因此 O(n) 复杂度，如果我对数组进行排序，则需要 O(n 2 )。
我总是可以使用 BST 进行 O(log(n)) 排序，但它们需要额外的空间来维护一棵树，我也可以创建一个堆并进行两次删除，我将获得第二大元素，但这里也创建了堆和存储在内存中。
我在这里有哪些选择？