剑指offer——43数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

题解：
　　目前想不出更好的方法，待续更新。。。

 class Solution {

 private:

     vector<int> min;

     vector<int> max;

 public:

         void Insert(int num)

         {

            int size=min.size()+max.size();

            if((size&)==)

            {

               if(max.size()> && num<max[])

               {

                  max.push_back(num);

                  push_heap(max.begin(),max.end(),less<int>());

                  num=max[];

                  pop_heap(max.begin(),max.end(),less<int>());

                  max.pop_back();

               }

               min.push_back(num);

               push_heap(min.begin(),min.end(),greater<int>());

            }

            else

            {

               if(min.size()> && num>min[])

               {

                 min.push_back(num);

                  push_heap(min.begin(),min.end(),greater<int>());

                  num=min[];

                  pop_heap(min.begin(),min.end(),greater<int>());

                  min.pop_back();

               }

               max.push_back(num);

               push_heap(max.begin(),max.end(),less<int>());

            }

         }

         double GetMedian()

         {

             int size=min.size()+max.size();

             if(size<=)

                 return ;

             if((size&)==)

                 return (max[]+min[])/2.0;

             else

                 return min[];

         }

 };

巴特西

剑指offer——43数据流中的中位数

最新文章

热门文章