Menu
Given a vector<T> vec{...} what's the best way to extract its minimum, maximum and median assuming T is one of the numeric types? I know of std::nth_element as well as std::minmax_element but they seem to do redundant work if called one after another.
The best idea I came up with so far is to just call std::nth_element 3 times one after another. But this still needs 3N comparisons, right? Is there any way to reuse the partial sorting done in previous iterations?
376
We traverse the array from i = 1 to n - 1 and compare each element with min and max. If (X[i] < min): We have found a value smaller than minimum till ith index. So update min with X[i] i.e min = X[i]. else If(X[i] > max): We have found a value greater than maximum till ith index.
Use Python's min() and max() to find smallest and largest values in your data. Call min() and max() with a single iterable or with any number of regular arguments. Use min() and max() with strings and dictionaries.
The min is simply the lowest observation, while the max is the highest observation. Obviously, it is easiest to determine the min and max if the data are ordered from lowest to highest. So for our data, the min is 13 and the max is 110.
Use std::nth_element to partition which yields the median, then std::min_element in the left half and std::max_element in the right one.
If you need it to be faster than that then roll your own version based on std::nth_element.
61
answered Oct 06 '22 06:10
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
