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

我相信有一种方法可以在O(n)中找到长度为n的未排序数组中的第k个最大元素.或许它是"预期的"O(n)或其他东西.我们应该怎么做？

1> 小智..：

---

这称为查找第k阶统计量.有一个非常简单的随机算法(称为quickselect),它采用O(n)平均时间,O(n^2)最坏情况时间和非常复杂的非随机算法(称为introselect)来获取O(n)最坏情况时间.维基百科上有一些信息,但它不是很好.

您需要的一切都在这些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等人的"算法入门"一书中,它也非常详细.

---

@eladv幻灯片链接坏了:(

---

@eladv请修复破损的链接.

---

谢谢你的幻灯片.

---

为什么它必须在5号工作？为什么它不适用于3号尺寸？

2> Ying Xiao..：

---

如果你想要一个真正的O(n)算法,而不是O(kn)类似的东西,那么你应该使用quickselect(它基本上是快速排序,你扔掉你不感兴趣的分区).我的教授有一个很好的写作,运行时分析:( 参考)

QuickSelect算法快速找到未排序n元素数组的第k个最小元素.它是一个RandomizedAlgorithm,因此我们计算最坏情况下的预期运行时间.

这是算法.

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

这个算法的运行时间是多少？如果对手为我们翻转硬币,我们可能会发现枢轴始终是最大的元素并k始终为1,运行时间为

T(n) = Theta(n) + T(n-1) = Theta(n2)

但如果选择确实是随机的,则预期的运行时间由下式给出

T(n) <= Theta(n) + (1/n) ?i=1 to nT(max(i, n-i-1))

我们正在做出一个不完全合理的假设,即递归总是落在较大的A1或者A2.

让我们猜T(n) <= an一下a.然后我们得到

T(n) 
 <= cn + (1/n) ?i=1 to nT(max(i-1, n-i))
 = cn + (1/n) ?i=1 to floor(n/2) T(n-i) + (1/n) ?i=floor(n/2)+1 to n T(i)
 <= cn + 2 (1/n) ?i=floor(n/2) to n T(i)
 <= cn + 2 (1/n) ?i=floor(n/2) to n ai

现在不知何故,我们必须在加号的右侧获得可怕的总和来吸收cn左边的.如果我们把它绑定为,我们粗略地得到.但这太大了 - 没有空间可以挤出额外的东西.那么让我们使用算术系列公式扩展总和:2(1/n) ?i=n/2 to n an2(1/n)(n/2)an = ancn

?i=floor(n/2) to n i  
 = ?i=1 to n i - ?i=1 to floor(n/2) i  
 = n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2  
 <= n2/2 - (n/4)2/2  
 = (15/32)n2

我们利用n"足够大"的优势来用floor(n/2)更清洁(更小)的方式取代丑陋的因素n/4.现在我们可以继续

cn + 2 (1/n) ?i=floor(n/2) to n ai,
 <= cn + (2a/n) (15/32) n2
 = n (c + (15/16)a)
 <= an

提供a > 16c.

这给了T(n) = O(n).很明显Omega(n),我们得到了T(n) = Theta(n).

---

Quickselect在平均情况下仅为O(n).在最坏的情况下,中位数中值算法可用于解决O(n)时间内的问题.

---

@MrROY鉴于我们在枢轴周围将"A"分为"A1"和"A2",我们知道`length(A)== length(A1)+ length(A2)+ 1`.因此,`k> length(A)-length(A2)`相当于`k> length(A1)+ 1`,当`k`在'A2'中某处时,这是真的.

3> warren..：

---

一个快速谷歌('第k大元素阵列')返回了这个:http://discuss.joelonsoftware.com/default.asp？interview.11.509587.17

"Make one pass through tracking the three largest values so far." 

(它专门用于3d最大)

这个答案:

Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)

---

好吧,它实际上是O(n)+ O(k log n),它对于K的显着值没有降低

---

但是在该双向链表中找到插入点是O(k).

4> 小智..：

---

你喜欢quicksort.随机选择一个元素并将所有内容推得更高或更低.此时你将知道你实际选择了哪个元素,如果它是你完成的第k个元素,否则你重复使用bin(更高或更低),第k个元素将落入.统计上讲,时间找到第k个元素随n,O(n)增长.

---

这就是quickselect,FWIW.

5> Jimmy..：

---

程序员的伴侣对算法分析给出了一个版本,是为O(n),虽然作者指出,常数因子是如此之高,你可能更喜欢天真排序的列表,然后选方法.

我回答了你的问题的信:)

---

在所有情况下都不是真的.我已经实现了中位数中位数,并将其与.NET中的内置Sort方法进行了比较,自定义解决方案的运行速度确实快了一个数量级.现在真正的问题是:在特定情况下,这对您来说是否重要.编写和调试100行代码与一个衬管相比,只有当代码要执行很多次以致用户开始注意到运行时间的差异并感到等待操作完成时感到不适时才能获得回报.

6> David Nehme..：

---

C++标准库几乎完全具有该函数调用nth_element,尽管它确实修改了您的数据.它预计线性运行时间为O(N),它也会进行部分排序.

const int N = ...;
double a[N];
// ... 
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a

---

不,这个答案没有任何问题.它有效,C++标准需要预期的线性运行时间.