[CareerCup][Google Interview] 寻找动态的中位数 - chkkch - 博客园
1. There is a stream of numbers, design an effective datastructre to store the numbers and to return the median at any point of time.
我们可以考虑维护一个max heap和一个min heap，max heap用来记录数组的前半部分, min heap用来记录数组的后半部分，返回数组的中位数时只要返回大堆的root。
当有一个新的数字进来时，可虑是否大于min heap的root，大于的话就放到min heap，它属于数组的后半部分，如果这时min heap的大小大于max heap了，则弹出root放到max heap里。
同时，如果新来的key小于max heap的root则放入大堆，并作相应调整。
整个算法的复杂度，插入O(logn)，提取O(1)
Read full article from [CareerCup][Google Interview] 寻找动态的中位数 - chkkch - 博客园
No comments:
Post a Comment