发现第n最小元素以阵列 [英] Finding n-th smallest element in an array

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on">How找到o在长度为n的排序的数组的第k最大元素（N）？

我目前正坐在一个课程作业的前面。 的任务是找到一个数组中第n最小元素。 （不排序它！）

I'm currently sitting in front of an course assignment. The task is to find the nth-smallest element in an array. (Without sorting it!)

我想了解BFPRT算法，但是从我得到了它是唯一有用的，如果你要计算的位数，而不是第n个最小元素。

I tried to understand the BFPRT algorithm but from what I got it is only useful if you want to calculate the median and not the "n-th smallest" element.

另一个想法我不得不，是通过将较小/较大节点到根节点的左/右的数组转换成树。我不知道但是如果这算作排序。 为了加速此我可以存储在每个节点的子节点的数量。

Another idea I had, was to convert the array into a tree by attaching smaller/bigger nodes to the left/right of the root node. I'm not sure however if this counts as sorting. To accelerate this I could store the number of subnodes in each node.

完整的任务还包括，该算法是递归的。 也有提示去想其他的数据结构。

The complete assignment also includes that the algorithm has to be recursive. There is also the hint to think about other data structures.

你觉得我的转化数组复制到一个平衡树的主意？

What do you think about my idea of transforming the array into a balanced tree?

是否还有其他的选择，我可能会错过？

编辑：我看了一下各种类似的问题，但没能完全理解的答案/它们应用到我的具体任务

I looked at various similar questions but were not able to completely understand the answers/apply them to my specific task.

推荐答案

传统的办法处理这一问题（的顺序统计问题的）让人想起快速排序的。比方说，你正在寻找的 K 的'个最小元素。挑选一个（随机）枢轴元件和分区其余元件分成两组（不含排序两组）：大号的包含小于或等于所述枢轴元件的所有元素（除了枢轴元件本身），和的的包含大于枢轴元件的所有元素。有多大的→的？如果它包含确切的 K - 1 的元素，则支点元素必须是 K 的'个最小的元素，和你做。如果的→的包含多个的 K - 1 的元素，那么 K 的'个最小的元素必须在→的;否则，它是在的的。现在，应用相同的算法，无论是的→或的（如果你需要使用的的，你必须调整的 K 因为你不再找的 K 的'个最小的，而 K 的'个整体最小的元素）。

The traditional approach to this problem (the order statistic problem) is reminiscent of quicksort. Let's say that you are looking for the k'th smallest element. Pick a (random) pivot element and partition the remaining elements into two groups (without sorting the two groups): L contains all elements that are smaller than or equal to the pivot element (except the pivot element itself), and G contains all elements that are greater than the pivot element. How large is L? If it contains exactly k - 1 elements, then the pivot element must be the k'th smallest element, and you are done. If L contains more than k - 1 elements, then the k'th smallest element must be in L; otherwise, it is in G. Now, apply the same algorithm to either L or G (if you need to use G, you must adjust k since you are no longer looking for the k'th smallest element of G, but the k'th smallest element overall).

该算法预期的 O（n）的运行的时间;不过，存在即保证的 O（N）的时间在最坏的情况下。

This algorithm runs in expected O(n) time; however, there exists a clever modification of the algorithm that guarantees O(n) time in worst case.

编辑：@Ishtar所指出的，聪明的修改的是的的BFPRT算法。它的核心思想是，以确保您永远不会选择坏支点元素，使得这两个分区的→和的不要变得太不平衡。只要人能保证一个分区将不会超过的比另一个大ç的时间（对于一些任意的，但固定的 C 的），运行时间将 O（N）的。

As @Ishtar points out, the "clever modification" is the BFPRT algorithm. Its core idea is to make sure that you never select a bad pivot element, such that the two partitions L and G do not become too unbalanced. As long as one can guarantee that one partition will never be more than c times larger than the other (for some arbitrary, but fixed c), the run time will be O(n).

这篇关于发现第n最小元素以阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！