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

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

我相信有一种方法可以在 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.