CODEWITHSUNDEEP
c++
Rob
Rob

Reputation: 171

Find n largest values in a vector

I currently have a vector and need to find the n largest numbers in it. For example, a user enters 5, i gotta run through it and output the 5 largest. Problem is, i can not sort this vector due to other constraints. Whats the best way to go about this?

Thanks!

Upvotes: 0

Views: 4980

Answers (3)

Qaz
Qaz

Reputation: 61910

Based on your description of not modifying the original vector and my assumption that you want the order to matter, I suggest std::partial_sort_copy:

//assume vector<int> as source
std::vector<int> dest(n); //largest n numbers; VLA or std::dynarray in C++14
std::partial_sort_copy(
    std::begin(source), std::end(source), //.begin/.end in C++98/C++03
    std::begin(dest), std::end(dest), 
    std::greater<int>() //remove "int" in C++14
);
//output dest however you want, e.g., std::copy

Upvotes: 9

Mats Petersson
Mats Petersson

Reputation: 129324

Something like this (A is incoming vector, N the number largest you want to find, v becomes the result vector):

vector<T> v(N, 0);   
for each element in A:
   if (element > v[N-1])
       for(i = N-1; i > 0 && v[i] < element; i--)
          v[i] = v[i-1];
       v[i] = element;

This is some sort of "pseudo-C++", not exactly C++, but hopefully describes how you'd do this.

Upvotes: 0

olydis
olydis

Reputation: 3310

Is copying and sorting an option? I mean if your application is not that performance critical, this is the simplest (and asymptotically not too bad) way to go!

Upvotes: 0

Related Questions