你可以用O(n + kn) = O(n)(对于常数k)表示时间，用O(k)表示空间，通过跟踪你见过的最大的k个元素。

对于数组中的每个元素，您可以扫描k个最大的元素列表，并将最小的元素替换为更大的新元素。

Warren的优先级堆解决方案更简洁。

    function nthMax(arr, nth = 1, maxNumber = Infinity) {
      let large = -Infinity;
      for(e of arr) {
        if(e > large && e < maxNumber ) {
          large = e;
        } else if (maxNumber == large) {
          nth++;
        }
      }
      return nth==0 ? maxNumber: nthMax(arr, nth-1, large);
    }

    let array = [11,12,12,34,23,34];

    let secondlargest = nthMax(array, 1);

    console.log("Number:", secondlargest);




   

在线性时间内找到数组的中值，然后使用与快速排序完全相同的划分程序将数组分为两部分，中值左边的值小于(<)中值，右边的值大于(>)中值，这也可以在线性时间内完成，现在，找到数组中第k个元素所在的部分， 现在递归式变成: T(n) = T(n/2) + cn 得到O (n) /。

Haskell的解决方案:

kthElem index list = sort list !! index

withShape ~[]     []     = []
withShape ~(x:xs) (y:ys) = x : withShape xs ys

sort []     = []
sort (x:xs) = (sort ls `withShape` ls) ++ [x] ++ (sort rs `withShape` rs)
  where
   ls = filter (<  x)
   rs = filter (>= x)

这通过使用withShape方法来实现中值解的中值，从而发现分区的大小，而无需实际计算分区大小。

如果你想要一个真正的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)

我会这样做:

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