如何在O（n）中长度为n的未排序数组中找到第k个最大元素？

  • Z时代
  • 2024-01-10
  • 分类：问答

我相信有一种方法可以找到O（n）中长度为n的未排序数组中的第k个最大元素。或者也许是“预期的” O（n）之类的东西。我们应该怎么做？

回答：

这称为查找第 。有一个非常简单的随机算法（称为 quickselect

），它占用了O(n)平均时间，O(n^2)最坏情况下的时间，还有一个相当复杂的非随机算法（称为 introselect

），它占用了O(n)最坏情况的时间。在Wikipedia上有一些信息，但这不是很好。

您需要的所有内容都在

这些PowerPoint幻灯片中。仅提取O(n)最坏情况算法的基本算法（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等人的《算法介绍》一书中，它也做了非常详细的介绍。

以上是 如何在O（n）中长度为n的未排序数组中找到第k个最大元素？ 的全部内容， 来源链接： utcz.com/qa/408239.html

回到顶部