0

I need to find the nth largest element in a range, which is not random access range, with O(1) extra space. The heap method takes too much space. I found a solution How to find the Kth smallest integer in an unsorted read only array? but it does not work for doubles. So is there a similar solution for doubles.

Thambi
  • 21
  • 5

2 Answers2

1

The key part is O(1) and possibly duplicate items. One possibility is:

Find the largest element smaller than the current maximum. Find the number of elements equal to this. Decrease until done.

Or in C-code something like:

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;
}

Another is to order the duplicates by keeping track of their index.

Hans Olsson
  • 11,123
  • 15
  • 38
0

If time does not matter:

Iterate the List n times and in each pass look for the largest element smaller than the one you found in the last pass.

If you want/need to handle duplicates you need a counter how often the all formerly searched largest elements occurred (all together = only one counter needed).

What size is your n that keeping a heap of n elements is not feasible option?

MrSmith42
  • 9,961
  • 6
  • 38
  • 49
  • @PopescuDavidIoan: why not ? –  Aug 23 '19 at 09:47
  • Because you look for something smaller than a value, not an element. i think this approach would give you the n-th largest value, not element. – Popescu David Ioan Aug 23 '19 at 10:02
  • Example : [2, 1, 3, 2, 3, 3], and n = 2. So we should iterate 2 times, the first iteration gives the value 3, and the second will give the value 2 ("look for the largest element smaller than the one you found in the last pass.") But the correct answer is 3, for that is the 2nd largest element. 2 is the 2nd largest value – Popescu David Ioan Aug 23 '19 at 10:05
  • 1
    @Popescu David Ioan: As described in my updated answer you can easily extend the idea to handle duplicates too. – MrSmith42 Aug 23 '19 at 11:12
  • The size is about 10 million. So heap is noy feasible. – Thambi Aug 24 '19 at 06:57
  • @Thambi: Depending on your datatype 10million entries need about 40megaBytes (if you implement it is an array). That should be no problem. – MrSmith42 Aug 27 '19 at 06:15