For array
[1,2,7,8,5]
, moving window size k = 3. return [2,7,7]
At first the window is at the start of the array like this
[ | 1,2,7 | ,8,5]
, return the median 2
;
then the window move one step forward.
[1, | 2,7,8 | ,5]
, return the median 7
;
then the window move one step forward again.
[1,2, | 7,8,5 | ]
, return the median 7
;
提示里面说到O(nlgn)的复杂度,加上求median,很自然地会想到用heap。关于如何用两个堆track中位数很多文章里都有解释。问题是heap不支持random remove操作,如果自己实现会比较麻烦。java中PriorityQueue是支持random remove的,所以就偷懒使用了;如果在面试中可以自己解释如何实现这个机制。
根据题意,median总是取N/2向下取整的,所以只要一直保持maxheap的size不小于minheap的size,这样每次只要取maxheap的堆顶。
另外要注意的是每次remove之后可能会造成两个heap的size不平衡,所以要重新resize
This comment has been removed by the author.
ReplyDelete