M smallest vector values ββwith size n (C ++ 11)
I need the average of the smallest values nClose
(other than the first zero) in a vector with elements n
where we know that nClose + 1 < n
, there are only non-negative numbers and the vector contains at least one zero value. Also, it nClose
will be much smaller n
, say nClose will be around 10 and n will be around 500.
I usually use min_element
to find the minimum, however this is useless here as I need multiple values. I am currently using the following code
sort(diff.begin(), diff.end());
double sum = accumulate(diff.begin() + 1, diff.begin() + 1 + nClose, 0);
double avg = sum / nClose;
Because of the sorting, it runs in O (n log n), where we can do it in O (nClose * n) by simply finding the minimum and removing it, then repeat that for nclose times. Know one of you how to do this with C ++ 11 algorithms?
source to share
You can use std::nth_element
for this.
nth_element(diff.begin(),diff.begin()+nClose+1, diff.end());
double sum = accumulate(diff.begin(), diff.begin() + 1 + nClose, 0);
double avg = sum / nClose;
Regarding your note about detecting the minimum and removing it: this is likely to be even less efficient than your current solution, since removing the nth element requires that all elements after moving the nth position be moved one position to the left, the algorithm into something like O (nClose * n ^ 2).
Also, while this should be a fairly efficient solution, I would caution you against putting too much weight on algorithmic complexity, since constants can play a much larger role than any advantage in Big O notation.
source to share