剑指offer63：数据流中的中位数

2 思路和方法

　　（1）用vector保存，get时先排序后取。插入排序复杂度O(nlogn） ，get时直接获取复杂度O(1)。Insert的实现：data.push_back(num); sort(data.begin(),data.end());　　GetMedian实现将依据有奇数个还是偶数个数据。偶数个数据返回 return (data[length/2]+data[length/2-1])/2;　　奇数个数据返回return data[(length/2)];

　　（2）分别用大顶堆和小顶堆保存左右两部分，左边一定比右边小，且左右两部分size之差不超过一，get时根据两边size情况去堆顶数据即可。插入复杂度O(logn)，get复杂度O(1）。

3 C++核心代码

 1 class Solution {
 2     vector<double> data;
 3 public:
 4     void Insert(int num)
 5     {
 6         data.push_back(num);
 7         sort(data.begin(),data.end());
 8     }
 9     double GetMedian()
10     {
11         int length = data.size();
12         if(length%2==0){
13             return (data[length/2]+data[length/2-1])/2;
14         }
15         else{
16             return data[(length/2)];
17         }
18     }
19 };

View Code

参考资料

https://blog.csdn.net/pynash123/article/details/89385675

https://blog.csdn.net/zjwreal/article/details/89290292