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

题目描述

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

方法一：查找排序法

思路：得到输入数组arr，可以获得len的长度，因此需要获得arr的前len/2数据量获得排序。

class Solution {
public:
    vector<int> arr;
    void Insert(int num)
    {
        arr.push_back(num);
    }

    double GetMedian()
    { 
        int len = arr.size();
        int mid = len / 2;
        for(int i = 0; i <= mid; i++){
            int min_index = i;
            for(int j = i + 1; j < len; j++){
                if(arr[j] < arr[min_index]){
                    min_index = j;
                }
            }
            if(min_index != i){
                int temp = arr[i];
                arr[i] = arr[min_index];
                arr[min_index] = temp;
            }
        }
        
        if(len % 2 == 0){
            return ((float)arr[mid] + (float)arr[mid - 1])/2;
        }
        return arr[mid];        
    }

};

方法二：暴力法

该方法的亮点：

1)static_cast<type>(level);方法，该方法将level转换成type类型；这里需要将int转换为double类型，因为中位数有可能出现小数；

2)sz是数组的长度，sz&1可以获取该int类型是否是奇数，因为只有奇数才会出现sz&1==True;

3)sz>>1使用位移的方式获得/2的效果，位移比除法效率高。

class Solution {
public:
    #define SCD static_cast<double>
    vector<int> arr;
    void Insert(int num)
    {
        arr.push_back(num);
    }
    double GetMedian()
    {
        sort(arr.begin(), arr.end());
        int sz = arr.size();
        if(sz & 1){
            return SCD(arr[sz>>1]);
        }else{
            return SCD(arr[sz>>1] + arr[(sz - 1)>>1]) / 2;
        }
    }
};

方法三：插入排序

思路：在插入数据的时候就对数据进行排序，使用插入排序法进行排序。

方法亮点：

1) lower_bound(first，last，val) 在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置.

2) upper_bound(first，last，val) 返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置;

3)binary_search(first，last，val) 返回的是在区间[first, last)中是否存在这么一个数val，返回一个bool值。

class Solution {
public:
    #define SCD static_cast<double>
    vector<int> arr;
    void Insert(int num)
    {
        if(arr.empty()){
            arr.push_back(num);
        }else{
            auto it = lower_bound(arr.begin(), arr.end(), num);
            arr.insert(it, num);
        }
    }
    double GetMedian()
    {
        int sz = arr.size();
        if(sz & 1){
            return SCD(arr[sz >>  1]);
        }else{
            return SCD(arr[sz >> 1] + arr[(sz - 1) >> 1]) / 2;
        }
    }
};

方法四：堆

中位数是指：有序数组中中间的那个数。则根据中位数可以把数组分为如下三段:
[0 ... median - 1], [median], [median ... arr.size() - 1]，即[中位数的左边，中位数，中位数的右边]

那么，如果我有个数据结构保留[0...median-1]的数据，并且可以O(1)时间取出最大值，即arr[0...median-1]中的最大值
相对应的，如果我有个数据结构可以保留[median + 1 ... arr.size() - 1] 的数据， 并且可以O(1)时间取出最小值，即
arr[median + 1 ... arr.size() - 1] 中的最小值。
然后，我们把[median]即中位数，随便放到哪个都可以。

假设[0 ... median - 1]的长度为l_len, [median + 1 ... arr.sise() - 1]的长度为 r_len.
1.如果l_len == r_len + 1, 说明，中位数是左边数据结构的最大值
2.如果l_len + 1 == r_len, 说明，中位数是右边数据结构的最小值
3.如果l_len == r_len, 说明，中位数是左边数据结构的最大值与右边数据结构的最小值的平均值。

说了这么多，一个数据结构可以O(1)返回最小值的，其实就是小根堆，O(1)返回最大值的，其实就是大根堆。并且每次插入到堆中的时间复杂度为O(logn)

所以，GetMedian()操作算法过程为：

• 初始化一个大根堆，存中位数左边的数据，一个小根堆，存中位数右边的数据
• 动态维护两个数据结构的大小，即最多只相差一个

代码如下：

class Solution {
public:
    #define SCD static_cast<double>
    priority_queue<int> min_q; // 大顶推
    priority_queue<int, vector<int>, greater<int>> max_q; // 小顶堆
 
    void Insert(int num)
    {
 
        min_q.push(num); // 试图加入到大顶推
 
        // 平衡一个两个堆
        max_q.push(min_q.top());
        min_q.pop();
 
        if (min_q.size() < max_q.si***_q.push(max_q.top());
            max_q.pop();
        }
 
    }
 
    double GetMedian()
    {
        return min_q.size() > max_q.size() ? SCD(min_q.top()) : SCD(min_q.top() + max_q.top()) / 2;
    }
 
};