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

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值

分析

由于数据是从一个数据流中读出来的，因而数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据，则当有新的数据从流中读出来时，这些数据就插入数据容器。那么该用什么数据容器呢？

• 数组

数组是最简单的数据容器。如果数组没有排序，则可以用Partition函数找出中位数。

1、在没有排序的数组中插入一个数字和找出中位数的时间复杂度分别是O(1)和O(n)。
2、如果往数组里插入新数据时让数组保持排序，由于可能需要移动O(n)个数。因此需要O(n)时间才能完成插入操作。在已经排好序的数组中查找中位数，只需O(1)时间

• 排序的链表

需要O(n)时间才能在链表中找到合适的位置插入。如果定义两个指针指向链表中间的结点，那么可以在O(1)时间得到中位数

• 二叉搜索树

二叉搜索树可以把插入新数据的平均时间降低到O(logn)，但是，当二叉搜索树极度不平衡从而看起来像一个排序的链表时，插入新数据的时间仍然是O(n)。为了得到中位数，可以在二叉树结点中添加一个表示子树结点数目的字段。有了这个字段，可以在平均O(logn)时间内得到中位数，但最差情况仍然需要O(n)

• 平衡二叉树（AVL树）

为了避免二叉搜索树的最差情况，还可以利用平衡二叉树，即AVL树。通常AVL树的平衡因子是左、右子树的高度差。可以稍做修改，把AVL树的平衡因子改为左、右子树结点数目之差。可以用O(logn)时间往AVL树中添加一个新结点，用O(1)时间得到所有结点的中位数

• 最大堆和最小堆

4png.png

如果能够保证数据容器左边的数据都小于右边的数据，那么即使左、右两边内部的数据没有排序，也可以根据左边最大的数和右边最小的数得到中位数。

用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据，同样，也可以在最小堆中找出最小值。

用一个最大堆实现左边的数据容器，用一个最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是O(logn)。由于只需要O(1)时间就可以得到位于堆顶的数据，因此，得到中位数的时间复杂度是O(1)。

1167904-20190112151510345-1764476192.png

算法实现

使用vector实现

template <typename T>
class DynamicArray {
public:
    // 插入数据
    void Insert(T number) {
        // 最小堆个数
        unsigned long minSize = min.size();
        // 最大堆个数
        unsigned long maxSize = max.size();

        // 为了实现平均分配，数据的总数据为偶数时插入最小堆
        if ((minSize + maxSize & 1) == 0) {
            // 插入元素小于最大值
            if (maxSize> 0 && number<max[0]) {
                // 添加到最大堆
                max.push_back(number);
                // 调整元素顺序成为最大堆
                push_heap(max.begin(), max.end(), less<T>());

                // 取出首元素最大值
                number = max[0];

                // 弹出堆顶元素
                pop_heap(max.begin(), max.end(), less<T>());
                max.pop_back();
            }

            // 插入最小堆
            min.push_back(number);
            // 调整最小堆
            push_heap(min.begin(), min.end(), greater<T>());
        } else { // 奇数时候，放入最大堆
            if (minSize > 0&& min[0] < number) {
                min.push_back(number);
                push_heap(min.begin(), min.end(), greater<T>());

                number=min[0];

                pop_heap(min.begin(), min.end(), greater<T>());
                min.pop_back();
            }

            // 最小值插入大根堆
            max.push_back(number);
            // 调整最大堆
            push_heap(max.begin(), max.end(), less<T>());
        }
    }

    // 获取中位数
    T GetMedian() {
        unsigned long size = min.size() + max.size();
        if (size==0) { // 没有元素，抛出异常
            throw "No number are available";
        }

        T median = 0; // 中位数
        if ((size & 1) == 1) { // 奇数个数
            median = min[0];
        } else { // 偶数个数
            median = (min[0] + max[0]) / 2;
        }

        return median;
    }

private:
    vector<T> min; // 最小堆
    vector<T> max; // 最大堆
};

使用priority_queue实现

class Solution {
public:
    // 插入数据
    void Insert(int num) {
        count += 1;

        if (count%2==0) { // 偶数个元素
            // 插入大顶堆
            bigHeap.push(num);
            // 获取大顶堆的最大画元素插入小顶堆
            smallHeap.push(bigHeap.top());
            // 弹出大顶堆首元素
            bigHeap.pop();
        } else {
            smallHeap.push(num);
            bigHeap.push(smallHeap.top());
            smallHeap.pop();
        }
    }

    // 获取中位数
    double GetMedian() {
        if (count & 0x1) {
            return bigHeap.top();
        } else {
            return (bigHeap.top() + smallHeap.top()) / 2.0;
        }
    }

private:
    int count = 0; // 元素个数
    priority_queue<int, vector<int>, less<int>> bigHeap; // 左边一个大顶堆
    priority_queue<int, vector<int>, greater<int>> smallHeap; // 右边一个小顶堆
};

参考

《剑指 offer》