algorithm - 在没有额外空间的未排序只读数据结构中找到第n个最大元素

我需要在一个范围内找到第n个最大的元素，这不是随机访问范围，有o（1）个额外的空间。堆方法占用太多空间我找到了一个How to find the Kth smallest integer in an unsorted read only array?的解决方案，但对双打不起作用。对于双打有类似的解决方案吗。

最佳答案

关键部分是O（1）和可能重复的项目一种可能性是：
找出小于当前最大值的最大元素。
找到与此相等的元素数。
减少直到完成。
或者用C代码，比如：

double findKthLargest(double arr[], int nElements, int k) {
   double currentMax, nextMax;
   int currentK=0, nDuplicates;
   for(;;) {
     nDuplicates=0;
     for(int j=0;j<nElements;++j) {
        if (currentK==0 || arr[j]<currentMax) {
           // Possible max
           if (j==0 || arr[j]>nextMax) nextMax=arr[j];
        }
     }
     for(int j=0;j<nElements;++j) if (arr[j]==nextMax) nDuplicates++;
     if (currentK+nDuplicates>=k) return nextMax;
     currentMax=nextMax;
     currentK=currentK+nDuplicates;
}

另一种方法是通过跟踪索引来对副本进行排序。

关于algorithm - 在没有额外空间的未排序只读数据结构中找到第n个最大元素，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57621296/