[牛客]数据流中的中位数

[牛客]数据流中的中位数

题目描述

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

大顶堆&小顶堆

思路分析

利用堆的知识，一个大顶堆（保存数据流中的前一半数），一个小顶堆（保存数据流中的后一半数）。这样，当数据流为偶数个时，结果为两个堆顶的平均值，当数据流为奇数个时，结果为大顶堆的堆顶。

我们需要维护这两个堆，保证：

1. 大顶堆的所有数比小顶堆小
2. 保证大顶堆的数量等于小顶堆的数量 或者 大顶堆的数量等于小顶堆的数量+1

代码

因为涉及大顶堆和小顶堆，还是用C++写方便，所以使用C++

class Solution {
public:
    priority_queue<int, vector<int>, greater<int>> minHeap;
    priority_queue<int, vector<int>, less<int>> maxHeap;
    void Insert(int num)
    {
        //如果大顶堆为空，或数小，优先进大顶堆
        if (maxHeap.empty()|| num<=maxHeap.top())
            maxHeap.push(num);
        else minHeap.push(num);
        //奇数个时，保证大顶堆的数量比小顶堆多1
        if (minHeap.size() == maxHeap.size()+1)
        {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
        //偶数个时，要维持两个堆的数量均衡
        if (minHeap.size() + 2 == maxHeap.size())
        {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }

    double GetMedian()
    { 
        if (minHeap.size() == maxHeap.size())
            return (minHeap.top()+maxHeap.top())/2.0;
        else
            return maxHeap.top();
    }
};

代码重点分析

1. 大顶堆、小顶堆的C++写法

priority_queue<int> q; //C++里默认是大顶堆
priority_queue<int, vector<int>, less<int>> maxHeap; //和上一行等价，大顶堆
priority_queue<int, vector<int>, greater<int>> minHeap; //小顶堆

这里要说明的是，C++里不标明比较逻辑时，默认是大顶堆。而python中q = Queue.PriorityQueue()默认是小顶堆。
其次，C++中的vector<int>不要丢失。

2. 精度损失的问题
   当数据流为偶数个时，需要算堆顶数据的平均值。
   return (minHeap.top()+maxHeap.top())/2;返回的结果是错误的，因为除以了int类型，造成精度损失。所以需要写成/2.0

快排思想，找第k个数

思路分析

使用快排的partition思想，每次确定一个数在序列中的位置，若大于k，则在该数左边的序列中继续找，若大于k，则在该数右边的序列中找。
当数的个数n为奇数时，我需要找到第n/2大的数（从0开始计数）。
当数的个数n为偶数时，我需要找到第n/2-1大的数和第n/2大的数（从0开始计数），取其平均值。

代码

class Solution {
    vector<int> numbers;
public:
    void Insert(int num){
        numbers.push_back(num);
    }
 
    int partition(int left, int right){
        if (left>=right)
            return left;
        int lo = left+1, hi = right;
        int pivot = numbers[left];
        while(lo <= hi){
            if (numbers[lo]>pivot)
                swap(numbers[lo], numbers[hi--]);
            else lo++;
        }
        swap(numbers[hi], numbers[left]);
        return hi;
    }
 
    int getNum(int k, int left, int right){
        int index = partition(left, right);
        while(index != k){
            if (index<k){
                left = index+1;
                index = partition(left, right);
            }
            else{
                right = index-1;
                index = partition(left, right);
            }
        }
        return numbers[index];
    }
    double GetMedian(){
        int len = numbers.size();
        if (len & 1 != 0) //奇
            return (double)getNum(len/2, 0, len-1);
        else{
            int num1 = getNum(len/2-1, 0, len-1);
            int num2 = getNum(len/2, len/2, len-1);
            return (num1+num2)/2.0;
        }
    }
};

代码重点分析

1. partition肯定要记牢的，多种场景下用处很大
2. 关于时间复杂度的分析
   
   假设，
   则
   
   所以时间复杂度为O(n)

参考

讨论区中马客(Mark)的代码
讨论区里还有手写AVL的，太优秀了