我相信有一种方法可以找到长度为n的O(n)无序数组中第k大的元素。也可能是期望O(n)之类的。我们该怎么做呢?
当前回答
对于k非常小的值(即k << n),我们可以在~O(n)时间内完成。否则,如果k与n比较,我们得到O(nlogn)
其他回答
首先,我们可以从未排序的数组中构建一个BST,它需要O(n)时间,从BST中我们可以找到O(log(n))中第k个最小的元素,它的总计数为O(n)。
你可以用O(n + kn) = O(n)(对于常数k)表示时间,用O(k)表示空间,通过跟踪你见过的最大的k个元素。
对于数组中的每个元素,您可以扫描k个最大的元素列表,并将最小的元素替换为更大的新元素。
Warren的优先级堆解决方案更简洁。
我会这样做:
initialize empty doubly linked list l
for each element e in array
if e larger than head(l)
make e the new head of l
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
您可以简单地存储指向链表中第一个和最后一个元素的指针。它们只在更新列表时更改。
更新:
initialize empty sorted tree l
for each element e in array
if e between head(l) and tail(l)
insert e into l // O(log k)
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
如果你想要一个真正的O(n)算法,而不是O(kn)或类似的算法,那么你应该使用快速选择(它基本上是快速排序,你会丢弃你不感兴趣的分区)。我的教授写了一篇很棒的文章,包括运行时分析:(参考)
QuickSelect算法可以快速找到包含n个元素的无序数组中的第k个最小元素。这是一个随机算法,所以我们计算最坏情况下的预期运行时间。
这是算法。
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中较大的那个。
让我们猜测对于某个a T(n) <= an,然后我们得到
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到n an,我们大致得到2(1/n)(n/2)an = an。但是这个太大了,没有多余的空间来挤进一个cn。让我们用等差级数公式展开和:
∑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“足够大”的优势,用更干净(更小)的n/4替换丑陋的地板(n/2)因子。现在我们可以继续
cn + 2 (1/n) ∑i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= an
提供了> 16c。
得到T(n) = O(n)显然是(n)所以我们得到T(n) = (n)
这种方法怎么样
保持一个长度为k的缓冲区和一个tmp_max,得到tmp_max为O(k)并执行n次因此类似于O(kn)
是这样还是我漏掉了什么?
虽然它没有击败快速选择的平均情况和中值统计方法的最坏情况,但它非常容易理解和实现。