如何在 O(n) 中找到长度为 n 的未排序数组中的第 k 个最大元素? [英] How to find the kth largest element in an unsorted array of length n in O(n)?

问题描述

我相信有一种方法可以在 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 个最大元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！