如何找到第k最大元素的长度为n的无序排列在O（n）的？

本文介绍了如何找到第k最大元素的长度为n的无序排列在O（n）的？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我相信有办法找到在长度的无序排列的n O（n）的第k个最大的元素。也许它的预期为O（n）或东西。我们怎样才能做到这一点？

I believe there's a way to find the kth largest element in an unsorted array of length n in O(n). Or perhaps it's "expected" O(n) or something. How can we do this?

推荐答案

这就是所谓发现在 K阶统计。有一个很简单的随机算法（所谓的 quickselect 的）采取 O（N）平均时间，和pretty的复杂的非随机算法回吐 O（N）最坏情况下的时间。有一个关于维基百科的一些信息，但它不是很好。

This is called finding the k-th order statistic. There's a very simple randomized algorithm (called quickselect) taking O(n) average time, and a pretty complicated non-randomized algorithm taking O(n) worst case time. There's some info on Wikipedia, but it's not very good.

您需要的一切都在这些PowerPoint幻灯片的。只是为了提取 O（N）最坏情况算法的基本算法：

Everything you need is in these powerpoint slides. Just to extract the basic algorithm of the O(n) worst-case algorithm:

Select(A,n,i): Divide input into ⌈n/5⌉ groups of size 5. /* Partition on median-of-medians */ medians = array of each group’s median. pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉) Left Array L and Right Array G = partition(A, pivot) /* Find ith element in L, pivot, or G */ k = |L| + 1 If i = k, return pivot If i < k, return Select(L, k-1, i) If i > k, return Select(G, n-k, i-k)

这也是非常好听通过Cormen等详细的算法导论的书。

It's also very nicely detailed in the Introduction to Algorithms book by Cormen et al.