-
April 6th, 2012, 11:12 AM
#1
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
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|