这种方法怎么样

保持一个长度为k的缓冲区和一个tmp_max，得到tmp_max为O(k)并执行n次因此类似于O(kn)

是这样还是我漏掉了什么?

虽然它没有击败快速选择的平均情况和中值统计方法的最坏情况，但它非常容易理解和实现。

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

遍历列表。如果当前值大于存储的最大值，则将其存储为最大值，并将1-4向下碰撞，5从列表中删除。如果不是，将它与第2条进行比较，然后做同样的事情。重复，检查所有5个存储值。应该是O(n)

下面是完整实现的链接，其中相当广泛地解释了在无序算法中查找第k个元素的算法是如何工作的。基本思想是像快速排序一样对数组进行分区。但为了避免极端情况(例如每一步都选择最小的元素作为主元，使算法运行时间退化为O(n^2))，采用特殊的主元选择，称为中位数的中位数算法。在最坏情况和平均情况下，整个解在O(n)时间内运行。

这里是全文的链接(它是关于寻找第k个最小的元素，但寻找第k个最大的元素的原理是相同的):

在无序数组中寻找第k个最小元素

    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大元素数组')上快速谷歌返回这个: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)