295. 数据流的中位数

😀最近新创建了个开源仓库，总结LeetCode的每日一题，目前已有C++、JavaScript语言版本，欢迎大家提供其他语言版本！ 🩲仓库地址：每日一题系列

题目描述：

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

例如，

[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

进阶:

1. 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？

2. 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

解答：

C++

方法一：暴力

暴力接法：直接尾部插入，sort快速排序，取中位数

class MedianFinder {
public:
    /** initialize your data structure here. */
    vector<int> mem_num;
    MedianFinder() {   
    }
    
    void addNum(int num) {
        this->mem_num.push_back(num);//插入
        sort(this->mem_num.begin(),this->mem_num.end());//快排
    }
    
    double findMedian() {
        int len=this->mem_num.size();
        //cout<<len<<endl;
        double mid_num=0;
        if(len%2==0){
            mid_num=(double(this->mem_num[len/2])+double(this->mem_num[len/2-1]))/2;
        }else if(len%2!=0){
            mid_num=double(this->mem_num[len/2]);
        }

        return mid_num;//中位数
    }
};

优化：二分插入，取中位数

class MedianFinder {
public:
    /** initialize your data structure here. */
    vector<int> mem_num;
    MedianFinder() {   
    }
    
    void addNum(int num) {
        auto addr=upper_bound(mem_num.begin(),mem_num.end(),num);
        mem_num.insert(addr,num);
    }
    
    double findMedian() {
        int len=this->mem_num.size();
        //cout<<len<<endl;
        double mid_num=0;
        if(len%2==0){
            mid_num=(double(this->mem_num[len/2])+double(this->mem_num[len/2-1]))/2;
        }else if(len%2!=0){
            mid_num=double(this->mem_num[len/2]);
        }

        return mid_num;
    }
};

方法二：优先队列

将数据分为两个优先队列（MIN与MAX）分别记录大于中位数的数和小于等于中位数的数，优先队列中的每个元素都有优先级，而优先级高（或者低）的将会先出队，而优先级相同的则按照其在优先队列中的顺序依次出队。

优先队列往往使用堆来实现

思路：First_num优先分配给MIN优先队列，New_num大于MIN.top()分配给MAX，若MAX.size()>MIN.size()把MAX.top()给MIN使两个优先队列的队头处于中位数位置；New_num小于等于MIN.top()分配给MIN，若MAX.size()<MIN.size()+1把MIN.top()给MAX使优使两个优先队列的队头处于中位数位置；返回队头即中位数

std::priority_queue默认由大根堆实现，即最大的数在堆顶，看下图：

class MedianFinder {
public:
    priority_queue<int> MIN;
    priority_queue<int, vector<int>,greater<int>> MAX;

    MedianFinder() {}

    void addNum(int num) {
        if (MIN.empty() || num <= MIN.top()) {
            MIN.push(num);
            if (MAX.size() + 1 < MIN.size()) {
                MAX.push(MIN.top());
                MIN.pop();
            }
        } else {
            MAX.push(num);
            if (MAX.size() > MIN.size()) {
                MIN.push(MAX.top());
                MAX.pop();
            }
        }
    }

    double findMedian() {
        if (MIN.size() > MAX.size()) {
            return MIN.top();
        }
        return (MIN.top() + MAX.top()) / 2.0;
    }
};

方法三：有序集+双指针

使用multiset有序集，并维护两个指针分别指向中位数的左右两个数，下程序指针维护未看懂，可以观察实例理解；

class MedianFinder {
    multiset<int> nums;//创建有序集
    multiset<int>::iterator left, right;//创建中位数的双指针

public:
    MedianFinder() : left(nums.end()), right(nums.end()) {}

    void addNum(int num) {
        int n = nums.size();//n为未插入大小
        nums.insert(num);//插入数据
        if (!n) {//有序集为空都指向头部
            left = right = nums.begin();
        } else if (n & 1) {//判断n为奇偶数，n奇数
            if (num < *left) {//此时，left与right指向同一个数，此时size()为偶数，新数小于左指针指向的数,所以left——;
                left--;
            } else {//此时，left与right指向同一个数，此时size()为偶数，新数大于左指针指向的数,所以right++;
                right++;
            }
        } else {//n为偶数
            if (num > *left && num < *right) {//此时，left与right指向左右两个数，此时size()为奇数，新数大于左指针指向的数,且小于右指针指向的数所以left++,right--，左右指向同一处;
                left++;
                right--;
            } else if (num >= *right) {//此时，left与right指向左右两个数，此时size()为奇数，新数大于右指针指向的数所以left++,左右指向同一处;
                left++;
            } else {//此时，left与right指向左右两个数，此时size()为奇数，新数小于左指针指向的数所以 right--,左右指向同一处;
                right--;
                left = right;
            }
        }
    }

    double findMedian() {
        return (*left + *right) / 2.0;
    }
};

JavaScript：

1. 使用两个堆，来存储数据流

2. 使用最小堆A保存较大的一半，最大堆B保存较小的一半

3. 若总长度N为奇数，则A个数为(N+1)/2，B个数为(N-1)/2

4. 若总长度N为偶数，则A个数为N/2，B个数为N/2

5. 插入操作：当N为偶数，需要向A添加一个元素，先将num插入B，再将B堆顶弹出，插入A

6. 插入操作：当N为奇数，需要向B添加一个元素，先将num插入A，再将A堆顶弹出，插入B

7. 中位数：可以由A和B的堆顶元素得到，若N为奇数，中位数=A的堆顶；若N为偶数，则中位数=(A的堆顶+B的堆顶)/2

const MedianFinder = function () {
    // 默认最大堆
    const defaultCmp = (x, y) => x > y;
    // 交换元素
    const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
    // 堆类，默认最大堆
    class Heap {
        constructor(cmp = defaultCmp) {
            this.container = [];
            this.cmp = cmp;
        }
        // 插入
        insert(data) {
            const { container, cmp } = this;
            container.push(data);
            let index = this.size() - 1;
            while (index) {
                let parent = (index - 1) >> 1;
                if (!cmp(container[index], container[parent])) {
                    return;
                }
                swap(container, index, parent);
                index = parent;
            }
        }
        // 弹出堆顶，并返回
        pop() {
            const { container, cmp } = this;
            if (!this.size()) {
                return null;
            }

            swap(container, 0, this.size() - 1);
            const res = container.pop();
            const length = this.size();
            let index = 0,
                exchange = index * 2 + 1;

            while (exchange < length) {
                // // 以最大堆的情况来说：如果有右节点，并且右节点的值大于左节点的值
                let right = index * 2 + 2;
                if (right < length && cmp(container[right], container[exchange])) {
                    exchange = right;
                }
                if (!cmp(container[exchange], container[index])) {
                    break;
                }
                swap(container, exchange, index);
                index = exchange;
                exchange = index * 2 + 1;
            }

            return res;
        }
        // 获取堆大小
        size() {
            return this.container.length;
        }
        // 获取堆顶
        peek() {
            if (this.size()) return this.container[0];
            return null;
        }
    }
    // 最小堆
    this.A = new Heap();
    // 最大堆
    this.B = new Heap((x, y) => x < y);
};

MedianFinder.prototype.addNum = function (num) {
    if (this.A.size() !== this.B.size()) {
        // 当N为奇数，需要向B添加一个元素
        // 先将num插入A，再将A堆顶弹出，插入B
        this.A.insert(num);
        this.B.insert(this.A.pop());
    } else {
        // 当N为偶数，需要向A添加一个元素
        // 先将num插入B，再将B堆顶弹出，插入A
        this.B.insert(num);
        this.A.insert(this.B.pop());
    }
};

MedianFinder.prototype.findMedian = function () {
    // 若总和为偶数，返回两个堆顶的平均数
    // 若总和为奇数，返回A的堆顶
    return this.A.container.length === this.B.container.length
        ? (this.A.peek() + this.B.peek()) / 2
        : this.A.peek();
};