我相信有一种方法可以在 O(n) 的长度为 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) 平均时间,O(n^2) 最坏情况时间,以及一个非常复杂的非随机算法(称为 introselect),它采用 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, O(n^2) worst case time, and a pretty complicated non-randomized algorithm (called introselect) taking O(n) worst case time. There's some info on Wikipedia, but it's not very good.
您需要的一切都在 这些幻灯片.只是为了提取O(n)最坏情况算法(introselect)的基本算法:
Everything you need is in these powerpoint slides. Just to extract the basic algorithm of the O(n) worst-case algorithm (introselect):
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.
更多推荐
如何在 O(n) 中找到长度为 n 的未排序数组中的第 k 个最大元素?
发布评论