CODEWITHSUNDEEP
c++algorithmc++11stlnth-element
aob
aob

Reputation: 197

Finding nth largest element inplace

I need to find nth largest element in an array and currently I'm doing it the following way:

std::vector<double> buffer(sequence); // sequence is const std::vector<double>
std::nth_element(buffer.begin(), buffer.begin() + idx, buffer.end(), std::greater<double>());
nth_element = buffer[idx];

But is there any way to find the n-th largest element in an array without using an external buffer?

Upvotes: 1

Views: 1619

Answers (2)

eerorika
eerorika

Reputation: 238311

You can avoid copying the entire buffer without modifying the original range by using std::partial_sort_copy. Simply copy the partially sorted range into a smaller buffer of size n, and take the last element.

If you may modify the original buffer, then you can simply use std::nth_element in place.

Upvotes: 10

Yuan Wen
Yuan Wen

Reputation: 1701

You can use the partition function used in Quick Sort to find the nth largest elements.

The partition function will divide the original array into two parts.The first part will be smaller than A[i], The second part will be larger than A[i],partition will return i.If i is equal to n, then return A[i].If i is smaller than n,then partition the second part.If i is larger than n,then partition the first part.

It won't cost you extra buffer,and the average time cost is O(n).

Upvotes: 0

Related Questions