力扣295.数据流的中位数[困难]

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

• void addNum(int num) - 从数据流中添加一个整数到数据结构中。
• double findMedian() - 返回目前所有元素的中位数。

  addNum(1)
  addNum(2)
  findMedian() -> 1.5
  addNum(3) 
  findMedian() -> 2
  

  

解法一：堆实现（B大顶堆和S小顶堆分别存放小数、大数）

        分析：使用优先队列保持有序结构，设元素总数为 N = m + n ，其中 m 和 n 分别为 S和 B 中的元素个数。

class MedianFinder {
public:
    priority_queue<int,vector<int>,greater<int>> S;//小顶堆
    priority_queue<int,vector<int>,less<int>> B;//大顶堆
    MedianFinder() {}
    
    void addNum(int num) {
        if(S.size()!=B.size()){//左边大数多了
            S.push(num);
            B.push(S.top());
            S.pop();
        }
        else{
            B.push(num);
            S.push(B.top());
            B.pop();            
        }
    }
    
    double findMedian() {
        return S.size()!=B.size()? S.top(): (S.top()+B.top())/2.0;
    }
};

解法二：有序队列+双指针

        我们把有序集合看作自动排序的数组，使用双指针指向有序集合中的中位数元素即可。当累计添加的数的数量为奇数时，双指针指向同一个元素。当累计添加的数的数量为偶数时，双指针分别指向构成中位数的两个数。

class MedianFinder {
public:
    MedianFinder() {left=nums.begin();right=nums.end();}
    void addNum(int num) {
        int len = nums.size();
        nums.insert(num);
        if(len<1){//数据为空
            left=right=nums.begin();
        }
        else if(len&1){//数据为奇数
            if(num<*left){
                left--;
            }
            else{
                right++;
            }
        }
        else{//数据为偶数，新添加的数字有三种情况，夹在原来偶数中间，分在左或者右
            // if(num<=*left){
            //     right--;
            //     //left=right;//这一步是针对，新插入值等于左侧的值，这时候这个值会插入到两个值的中间,set的重复值插入到原来数值的右边
                                //可以使用 num<*left 在判断的时候将其归类为第三类中间值去处理
            // }
            if(num<*left){
                right--;
            }            
            else if(num>=*right){
                left++;
            }
            else{
                left++;right--;
            }
        }
    }
    
    double findMedian() {
        return (*left+*right)/2.0;
    }
private:
    multiset<int> nums;
    multiset<int> ::iterator left ,right;
};

解法三：存储时保持有序（超时）

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
    }
    
    void addNum(int num) {
        int i=0;
        //while (i<res.size() && res[i] < num) i++;
        for(i;i<res.size();i++){
            if(res[i]>=num){
                break;
            }
        }
        res.insert(res.begin()+i, num);
    }
    
    double findMedian() {
        if (res.empty()) return NULL;
        if (res.size() % 2) return res[res.size()/2];
        return (res[res.size()/2] + res[res.size()/2 -1] )/2.0;
        
    }
private:
    vector<int> res;
};

解法四：私调用快速排序（超时）

class MedianFinder {
public:
    /** initialize your data structure here. */
    vector<double> res;
    MedianFinder() {}//默认构造
    
    void addNum(int num) {
         res.push_back(num);
    }
 
    double findMedian() {
        int len = res.size();
        if(len<1){
            return 0;
        }
        //sort(res.begin(),res.end());这个时间会超时
        quicksort(res,0,len-1);
        if(len%2==0){
            return (res[len/2]+res[len/2-1])/2;
        }
        else{
            return res[(len-1)/2];
        }
    }
private:
    void quicksort(vector<double> &arr,int l,int r){
        if(l>r)return;
        int i=l,j=r;
        while(i<j){
            while(i<j&&arr[j]>=arr[l])j--;
            while(i<j&&arr[i]<=arr[l])i++;
            swap(arr[i],arr[j]);
        }
        swap(arr[i],arr[l]);
        quicksort(arr,l,i-1);
        quicksort(arr,i+1,r);
    }
};