剑指offer(C++)-JZ41：数据流中的中位数(算法-排序)

**剑指Offer-JZ41: 数据流中的中位数**

在这个问题中，我们需要实现一个数据流类，能够实时计算出当前数据流中的中位数。中位数是指如果数据流中的数字按顺序排列，则中间的那个数字。如果数据流中的数字总数为奇数，则中位数就是中间的那个数字；如果数据流中的数字总数为偶数，则中位数是中间两个数字的平均值。

**算法思路**

由于需要实时计算中位数，我们不能简单地将所有数据都存储在内存中，然后再进行排序和求中位数。这样做会导致空间复杂度过高，甚至可能导致内存溢出。

一种解决方案是使用一个大小为 n 的堆（大顶堆或小顶堆）来存储当前数据流中的数字，其中 n 是当前数据流中的数字总数。如果 n 为奇数，则中位数就是堆顶的数字；如果 n 为偶数，则中位数是堆顶和堆第二大的数字的平均值。

**C++代码实现**

cpp#include <iostream>
#include <vector>

class MedianFinder {
public:
 // 大顶堆，存储当前数据流中的小于或等于当前中位数的数字 std::priority_queue<int> maxHeap;
 // 小顶堆，存储当前数据流中的大于当前中位数的数字 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

 void addNum(int num) {
 // 如果 maxHeap 中的数字总数小于或等于 minHeap 中的数字总数，则将 num 加入 maxHeap if (maxHeap.size() <= minHeap.size()) {
 maxHeap.push(num);
 } else {
 minHeap.push(num);
 }
 //重新调整堆，确保 maxHeap 和 minHeap 中的数字总数相等 balanceHeaps();
 }

 double findMedian() {
 if (maxHeap.empty() && minHeap.empty()) {
 return0.0;
 } else if (maxHeap.size() == minHeap.size()) {
 // 如果 maxHeap 和 minHeap 中的数字总数相等，则中位数是 maxHeap 和 minHeap 的堆顶数字的平均值 return (double)(maxHeap.top() + minHeap.top()) /2.0;
 } else if (maxHeap.size() > minHeap.size()) {
 // 如果 maxHeap 中的数字总数大于 minHeap 中的数字总数，则中位数是 maxHeap 的堆顶数字 return maxHeap.top();
 } else {
 // 如果 minHeap 中的数字总数大于 maxHeap 中的数字总数，则中位数是 minHeap 的堆顶数字 return minHeap.top();
 }
 }

private:
 void balanceHeaps() {
 if (maxHeap.size() > minHeap.size() +1) {
 // 如果 maxHeap 中的数字总数大于 minHeap 中的数字总数加一，则将 maxHeap 的堆顶数字加入 minHeap int num = maxHeap.top();
 maxHeap.pop();
 minHeap.push(num);
 } else if (maxHeap.size() +1 < minHeap.size()) {
 // 如果 minHeap 中的数字总数大于 maxHeap 中的数字总数加一，则将 minHeap 的堆顶数字加入 maxHeap int num = minHeap.top();
 minHeap.pop();
 maxHeap.push(num);
 }
 }
};

cppint main() {
 MedianFinder medianFinder;
 // 添加数字到数据流中 medianFinder.addNum(1);
 medianFinder.addNum(2);
 medianFinder.addNum(3);
 // 查找当前数据流中的中位数 double median = medianFinder.findMedian();
 std::cout << "Current median: " << median << std::endl;
 return0;
}