我们怎样才能找到数组中最重要的元素？
使用数据结构自平衡二叉搜索树查找数组中第n个最小/最大元素的算法
阅读post： 以最佳方式在二叉搜索树中查找第k个最小元素 。 但正确的答案并不清楚，因为我无法弄清楚正确答案，我拿了一个例子……请多说明一点……
CAR Hoare的select算法就是为了这个目的而设计的。 它在[预期]线性时间内执行，具有对数额外存储。
编辑：排序的明显替代方案，然后选择正确的元素具有O（N log N）复杂度而不是O（N）。 以排序顺序存储i最大元素需要O（i）辅助存储，并且大致为O（N * i log i）复杂度。 如果i 先验地知道非常小（例如1或2），这可能是一个胜利。 对于更一般的用途， select通常更好。
编辑2：随便，我没有很好的参考，但在前一个答案中描述了这个想法。
首先对数组进行降序排序，然后取第i个元素。
创建一个排序数据结构来保存i元素并将初始计数设置为0。
处理源数组中的每个元素，将其添加到该新结构，直到新结构已满。
然后处理源数组的其余部分。 对于每个大于排序数据结构中最小值的结构，从该结构中删除最小值并将新结构放入其中。
一旦处理完源数组中的所有元素，您的结构将保存最大的元素。 抓住最后一个，你就拥有了i最伟大的元素。
瞧！
或者，对它进行排序然后直接抓取第i个元素。
对于具有非常低插入和低delete_min成本的堆来说，这是一个合适的任务。 例如配对堆 。 它将具有最坏的情况O（n * log（n））性能。 但是既然要实现非平凡，最好先检查别处选择算法 。
有许多策略可用于您的任务（如果您不首先关注自平衡树）。
它通常是权衡速度/内存。 大多数算法要么需要修改arrays，要么修改O(N)附加存储。
具有自平衡树的解决方案属于后一类，但这不是正确的选择。 问题是构建树本身需要O(N*log N) ，这将主导后面的搜索项并给出O(N*log N)的最终复杂度。 因此，您不仅仅是简单地对数组进行排序并使用复杂的数据结构……
一般来说，这个问题在很大程度上取决于与N相关的i的大小。 如果你想一分钟，对于i == 1它是微不足道的吗？ 它被称为寻找最大值。
那么，相同的策略显然适用于线性时间中i == 2 （携带2个最大元素）。 而且它也是平凡对称的：即如果你需要找到第N-1个元素，那么只需携带2个最小元素。
然而，当i约为N / 2或N / 4时，它会失去效率。 携带i最大元素然后意味着排序大小i的数组…因此我们回退N*log N墙。
Jerry Coffin指出了一个简单的解决方案，适用于这种情况。 这是维基百科的参考。 完整的文章还描述了中位数中位数方法：它更可靠，但涉及更多工作，因此通常较慢。
Create an empty list L For each element x in the original list, add x in sorted position to L if L has more than i elements, pop the smallest one off L if List2 has i elements, return the i-th element, else return failure
这应该取O（N（log（i）））。 如果我被认为是常数，则它是O（N）。
从元素构建堆并调用MIN i次。