Most efficient way to find iterators of 4 maximum values in const vector in C++

user_11145191 0
Viewed 112

I have to find 4 the biggest numbers in a const vector and return their positions. I want this code to have the best time and space complexity. My first idea is to copy this const vector into vector and bubble sort it 4 times. That gives me 4*N but i have to create a vector. Second idea is to put everything from this const vector into priority_queue. That gives me a N*log2(N) time complexity without creating another variables. The maximum of N is around 100.

Is there any other options to do it in the fastest and the least space-consuming way?

EDIT: It doesn't matter which one is the biggest, I just need to return position of this 4 items in the input vector.

vector complexity-theory constants c++
4 Answers

O(n) solution

std::vector<int>::iterator max1 = v.begin(), max2 = v.begin(), max3 = v.begin(), max4 = v.begin();
for(std::vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    if((*max1) < (*it)) {
        max4 = max3;
        max3 = max2;
        max2 = max1;
        max1 = it;
    } else if((*max2) < (*it)) {
        max4 = max3;
        max3 = max2;
        max2 = it;
    } else if((*max3) < (*it)) {
        max4 = max3;
        max3 = it;
    } else if((*max4) < (*it)) {
        max4 = it;
    }
}
user_72953370

You can implement this quite easily with an extra vector, and the nth_element algorithm, which is O(n) time:

std::vector<int> const v = ...;

// create a vector of elements with original indexes
std::vector<std::pair<int,int>> res;

// populate the result vector
int k = 0;
for (int i : v)
  res.push_back({i,k++});

// find the maximum 4 elements
std::nth_element(res.begin(), res.begin() + 4, res.end(),
   [](auto const &a, auto const &b) { return a.first > b.first; });

Here's a demo.

Note that this solution uses O(n) extra space. If N grows large, then this might not be the right approach for finding just 4 largest elements. It's still a good approach if you want the M largest elements, where M grows like N.

user_83728530

Yes, use a heap of size four. Then you iterate through the vector and update the heap accordingly.

Sample code using std heap methods and finding minimum values (from here) follows.

const std::vector<int> input;
const size_t n = 4;
std::vector<int> ret(n);
auto dfirst = ret.begin(), dlast = ret.end();

// initialize heap with infinity distances
std::fill(dfirst, dlast, 100000000000); // do better here

for (auto it = input.begin(); it != input.end(); ++it)
{
    if (*it < *dfirst) {
        // remove max. value in heap
        std::pop_heap(dfirst, dlast); // add comparator as third arg

        // max element is now on position "back" and should be popped
        // instead we overwrite it directly with the new element
        *(dlast-1) = *it;
        std::push_heap(dfirst, dlast); // add comparator as third arg
    }
}
std::sort_heap(dfirst, dlast); // remove if not needed, or add comparator as third arg
return ret;

Adapt accordingly:

  • Use a pair of index, value in the heap to keep track of positions which you like to return
  • Use comparator that compares on value in the pair and establishes a desc. ordering

This is more generic than @Jugal Rawlani's solution if your number n might change/grow in the future. Otherwise his idea wins.

ypnos_219740

read the 4 first elements into a vector of 4. sort this vector so that minimum of the 4 is in index 0.

loop on remaining items of the const vector, if current value > min, replace it and re-sort the 4 element vector

user_117239650
Related