April 6th, 2012, 12:12 PM
find the median in a fix-sized moving window on a long sequency of data
Given a sequence of data (it may have duplicates), a fixed-sized moving window, move the window at each iteration from the start of the data sequence, such that (1) the oldest data element is removed from the window and a new data element is pushed into the window (2) find the median of the data inside the window at each moving.
I can use 2 binary search trees to do it. it is O(n lg m), where m is window size.
I am wondering if there is a O(n) time algorithm .
Any help is appreciated.
Tags for this Thread
Click Here to Expand Forum to Full Width