39 lines
1.1 KiB
C++
39 lines
1.1 KiB
C++
#include <bits/stdc++.h>
|
|
#include <ext/pb_ds/assoc_container.hpp>
|
|
#include <ext/pb_ds/tree_policy.hpp>
|
|
|
|
// the std::less_equal<> comparator allows the tree to support duplicates
|
|
typedef __gnu_pbds::tree<double, __gnu_pbds::null_type, std::less_equal<double>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ost_t;
|
|
|
|
// The lookup method, find_by_order (aka Select), is O(log n) for this data structure, much faster than std::nth_element()
|
|
double median(ost_t &OST)
|
|
{
|
|
int n = OST.size();
|
|
int m = n/2;
|
|
if (n == 1)
|
|
return *OST.find_by_order(0);
|
|
if (n == 2)
|
|
return (*OST.find_by_order(0) + *OST.find_by_order(1)) / 2;
|
|
|
|
if (n & 1) // odd number of elements
|
|
return *OST.find_by_order(m);
|
|
else // even number of elements
|
|
return (*OST.find_by_order(m) + *OST.find_by_order(m-1)) / 2;
|
|
}
|
|
|
|
int main(int argc, char* argv[])
|
|
{
|
|
ost_t ostree;
|
|
|
|
// insertion is also O(log n) for OSTs
|
|
ostree.insert(4.1);
|
|
ostree.insert(7.2);
|
|
ostree.insert(1.7);
|
|
ostree.insert(9.3);
|
|
ostree.insert(4.4);
|
|
ostree.insert(3.2);
|
|
|
|
printf("%.3f\n", median(ostree)); // 4.250
|
|
|
|
return 0;
|
|
}
|