Open rheineke opened 7 years ago
For integral types (or objects that support an integral hash?), a running median can be calculated using counting sort. It requires auxiliary storage space, and seems to run in linear time, but linear in keys rather than items (verify).
http://stackoverflow.com/questions/10657503/find-running-median-from-a-stream-of-integers
rheineke
commented
7 years ago
For integral types (or objects that support an integral hash?), a running median can be calculated using counting sort. It requires auxiliary storage space, and seems to run in linear time, but linear in keys rather than items (verify).