当前位置：首页>后端>正文

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

后端2024-04-23 00:10:50

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

题目描述

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

大顶堆&小顶堆

思路分析

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

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

大顶堆的所有数比小顶堆小
保证大顶堆的数量等于小顶堆的数量或者大顶堆的数量等于小顶堆的数量+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();
    }
};

代码重点分析

大顶堆、小顶堆的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>不要丢失。

精度损失的问题
当数据流为偶数个时，需要算堆顶数据的平均值。
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;
        }
    }
};

代码重点分析

partition肯定要记牢的，多种场景下用处很大
关于时间复杂度的分析
$[牛客]数据流中的中位数,T(n) = T(n/2) + O(n),第1张$
假设 $[牛客]数据流中的中位数,n = 2^k,第2张$ ，
则
$[牛客]数据流中的中位数,\begin{align} T(2^k) &= T(2^{k-1}) + O(2^k)\ &= T(2^{k-2}) + O(2^{k-1}) + O(2^k) \ &= T(2^0) + O(2^0) + O(2^1) + O(2^2) + \cdots + O(2^k) \ &= 1+O(2^0 + 2^1 + 2^2 + \cdots + 2^k) \ & = O(2^{k+1} - 1) \ & = O(2 \times n -1) \ & = O(n) \end{align},第3张$
所以时间复杂度为O(n)