如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。

IDEA

1.采用插入排序，插入一個(gè)，調(diào)整一次順序；

2.兩個(gè)堆實(shí)現(xiàn)。一個(gè)大頂堆，一個(gè)小頂堆，大頂堆中所有數(shù)<=小頂堆中所有數(shù)。

CODE

1.

class Solution {PRivate:    vector<int> vec;    int n;public:    void Insert(int num)    {        vec.push_back(num);        n=vec.size();        int i=n-1;        while(i>0&&vec[i]<vec[i-1]){            int tmp=vec[i-1];            vec[i-1]=vec[i];            vec[i]=tmp;            i--;        }     }    double GetMedian()    {         return (vec[n/2]+vec[(n-1)/2])/2.0;    }};2.
class Solution {private:    int count=0;    priority_queue<int,vector<int>,less<int> >big_heap;    priority_queue<int,vector<int>,greater<int> >small_heap;public:    void Insert(int num)    {        count++;        if(count%2){            small_heap.push(num);            big_heap.push(small_heap.top());            small_heap.pop();                    }else{            big_heap.push(num);            small_heap.push(big_heap.top());            big_heap.pop();        }    }    double GetMedian()    {         if(count%2){            return big_heap.top();        }else{            return (big_heap.top()+small_heap.top())/2.0;        }    }};