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

Question

我需要在一个范围内找到第 n 个最大的元素，该范围不是随机访问范围，额外空间为 O(1)。堆方法太占空间了。我找到了解决方案 How to find the Kth smallest integer in an unsorted read only array?但它不适用于 double 。那么 double 有没有类似的解决方案。

Answer 1

关键部分是 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;
}

另一种方法是通过跟踪索引来对重复项进行排序。