leetcode295：数据流的中位数

题目链接

leetcode

题目描述

中位数是有序整数列表中的中间值。
如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;

/*
    对于海量数据流，使用最大堆和最小堆来管理，把数据分为[小]|[大]两部分。
    最大堆保存前半部分的最大值，最小堆保存后半部分的最小值。
    保证左边和右边的个数之差不大于 1，并且左边大于右边。
    
    时间复杂度：O(logn)
        添加操作的时间复杂度是 O(logn)，需要在堆中插入元素，在两个堆之间转移元素。
        查找操作的时间复杂度是 O(1)，需要访问堆顶元素。
        每个元素的添加和查找操作，时间复杂度是 O(logn) 和 O(1)。
        整个数据流，添加 n 个元素，时间复杂度是 O(nlogn)。
    空间复杂度：O(n)
        最坏情况下，所有元素都存储在一个堆。
*/
class MedianFinder {
public:
    MedianFinder() {

    }
    
    void addNum(int num) {
        if (maxHeap.size() == minHeap.size()) {
            // 两个堆元素数量相等，先加入 minHeap 再移动到 maxHeap
            minHeap.push(num);
            maxHeap.push(minHeap.top());
            minHeap.pop();
        } else {
            // maxHeap 多一个元素，把新元素加到 maxHeap，再调整到 minHeap
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        } else {
            return maxHeap.top();
        }
    }

private:
    priority_queue<int, vector<int>, less<int>> maxHeap;    // 大根堆（默认），存储较小的一半元素
    priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆，存储较大的一半元素
};

// 辅助函数：打印数组
void printArray(const vector<string>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "\"" << nums[i] << "\"";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    MedianFinder medianFinder;
    vector<string> operations = {"MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"};
    vector<vector<int>> params = {{}, {1}, {2}, {}, {3}, {}};
    vector<string> output;

    for (int i = 0; i < operations.size(); i++) {
        if (operations[i] == "MedianFinder") {
            // 创建 MedianFinder 实例，已在 main 函数中创建
            output.push_back("null");
        } else if (operations[i] == "addNum") {
            medianFinder.addNum(params[i][0]);
            output.push_back("null");
        } else if (operations[i] == "findMedian") {
            double median = medianFinder.findMedian();
            stringstream ss;
            ss << fixed << setprecision(1) << median; // 设置浮点数输出精度为1位小数
            output.push_back(ss.str());
        }
    }

    cout << "Input: " << endl;
    printArray(operations);
    cout << endl;
    printArray(params);
    cout << endl;
    cout << "Output: " << endl;
    printArray(output);
    cout << endl;

    return 0;
}