我们如何才能找到数组的第i个最大元素？ [英] How can we find the i'th greatest element of the array?

问题描述

算法使用数据strucuture自阵列中的第n个查找最小/最大元素平衡二叉搜索树。

Algorithm for Finding nth smallest/largest element in an array using data strucuture self balancing binary search tree..

阅读帖子：<一href=\"http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way/2329236#2329236\">http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way/2329236#2329236.但是，正确的答案是不明确的，因为我无法找出正确的答案，对于一个例子，我花了......请需要进一步的解释.......

Read the post: http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way/2329236#2329236. But the correct answer is not clear, as i am not able to figure out the correct answer, for an example that i took...... Please a bit more explanation required.......

推荐答案

C.A.R。霍尔的选择算法是专为precisely这一目的。它执行在[预计]线性时间，用对数额外的存储空间。

C.A.R. Hoare's select algorithm is designed for precisely this purpose. It executes in [expected] linear time, with logarithmic extra storage.

编辑：排序，然后挑选合适元素的替代明显有O（N日志N）的复杂性，而不是O（N）。存储 I 在有序最大的元素需要O（I）辅助存储器，大约O（N *我登录我）的复杂性。这的可以的是一个双赢，如果 I 众所周知的先验的相当小（例如1或2）。更普遍的应用，选择通常是更好的。

the obvious alternative of sorting, then picking the right element has O(N log N) complexity instead of O(N). Storing the i largest elements in sorted order requires O(i) auxiliary storage, and roughly O(N * i log i) complexity. This can be a win if i is known a priori to be quite small (e.g. 1 or 2). For more general use, select is usually better.

EDIT2：随便，我没有为它一个很好的参考，但在<一个描述的想法href=\"http://stackoverflow.com/questions/3074372/recur-by-using-the-pivot-in-select-algorithm/3074394#3074394\">$p$pvious回答。

offhand, I don't have a good reference for it, but described the idea in a previous answer.

这篇关于我们如何才能找到数组的第i个最大元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！