Google – Moving Window Max Median
找moving window的最大median.
[Analysis]
这道题和leetcode里的find median from data stream不一样，data stream是不需要删除元素的，维护两个heap，一直不停的往里插入就可以了。
但是moving window需要删除元素，那么heap就不是很好的选择了，因为Heap根本就不支持删除操作，硬要从底层来删的话，复杂度就上去了。
[Solution]
这道题最好的方法是用hash heap，这样删除操作可以在O(1)时间完成，插入和rebalance都是O(logm)，m是window size。get Median也是O(1)时间。
还有一种方法是用两个bst，不过实现起来略显复杂，首先要维护两个变量表示第一个bst的最大值和第二个bst的最小值，这样才能确保get median的时间是O(1)。这两个变量在每次插入删除的时候都需要更新。
但用bst的话，插入删除都是O(logm)，还没有hash heap好。
Read full article from Google – Moving Window Max Median
No comments:
Post a Comment