leetcode 295. 数据流的中位数

时间复杂度分析：为什么你的中位数查找方案会超时？

分析你提供的MedianFinder实现，其时间复杂度较高的原因主要在于findMedian函数的实现方式。让我详细解释：

代码时间复杂度分析

你的代码中两个主要函数的时间复杂度如下：

1. addNum函数：

   void addNum(int num) {nums.emplace_back(num);
   }
   

   • 时间复杂度：O(1)
   • 解释：将数字添加到vector末尾，是常数时间操作

2. findMedian函数：

   double findMedian() {if (nums.size() <= 0) {return 0.0;}sort(nums.begin(), nums.end()); // 关键性能瓶颈auto n = nums.size();if (n % 2) {return nums[n / 2];} else {return (nums[n / 2] + nums[(n - 1) / 2]) / 2.0;}
   }
   

   • 时间复杂度：O(n log n)，其中n是当前数字的个数
   • 解释：每次查找中位数时都对整个数组进行排序，排序的时间复杂度是O(n log n)

为什么这个时间复杂度无法通过？

LeetCode 295题「寻找中位数」的测试用例通常包含大量操作。假设：

• 进行m次addNum操作和m次findMedian操作
• 你的实现总时间复杂度为O(m * n log n)，其中n是数据规模

当m和n较大时（例如10^5次操作），这样的复杂度会导致超时。具体来说：

• 对于10^5次操作，O(n log n)的复杂度意味着约10^5 * 10^5 log 10^5 ≈ 10^{10次操作，这远远超过了LeetCode的时间限制（通常要求算法在10}8次操作内完成）

优化方案：使用双堆实现

为了将时间复杂度优化到更高效的水平，我们可以使用两个堆（大顶堆和小顶堆）来维护数据：

• 大顶堆maxHeap保存较小的一半数字
• 小顶堆minHeap保存较大的一半数字
• 确保两个堆的大小差不超过1，这样堆顶元素就是中位数

class MedianFinder {
private:priority_queue<int> maxHeap; // 大顶堆，保存较小的一半数字priority_queue<int, vector<int>, greater<int>> minHeap; // 小顶堆，保存较大的一半数字public:MedianFinder() {}void addNum(int num) {// 平衡两个堆的大小if (maxHeap.empty() || num <= maxHeap.top()) {maxHeap.push(num);} else {minHeap.push(num);}// 调整堆的大小，使两个堆的大小差不超过1if (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();}}double findMedian() {if (maxHeap.size() > minHeap.size()) {return maxHeap.top();} else {return (maxHeap.top() + minHeap.top()) / 2.0;}}
};

优化后时间复杂度分析

• addNum函数：O(log n)

  • 堆的插入和弹出操作都是O(log n)
  • 每次添加数字后最多进行一次堆调整

• findMedian函数：O(1)

  • 直接返回堆顶元素，无需排序

空间复杂度

• O(n)，其中n是存储的数字个数
• 需要两个堆来存储数据

这种双堆实现能够高效处理大量的添加和查询操作，轻松通过LeetCode的时间限制。关键在于避免了每次查询都进行排序，而是通过堆结构维护数据的有序性。

在C++中，小顶堆（最小堆）的确可以通过std::priority_queue结合std::greater<int>来实现。下面详细解释其原理和用法：

一、小顶堆与greater<int>的关系

1. 堆的基本概念

• 堆是一种完全二叉树，分为两种：
  • 大顶堆：每个节点的值都大于或等于其子节点的值，堆顶是最大值。
  • 小顶堆：每个节点的值都小于或等于其子节点的值，堆顶是最小值。

2. std::priority_queue的模板参数

std::priority_queue的默认实现是大顶堆，其模板定义为：

template <class T,class Container = vector<T>,class Compare = less<T>
> class priority_queue;

• T：元素类型。
• Container：存储元素的容器（默认用vector）。
• Compare：比较函数（默认用less<T>，即大顶堆）。

3. 小顶堆的实现

将Compare参数改为greater<T>即可实现小顶堆：

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

• greater<int>是一个函数对象，用于比较两个整数，当a > b时返回true，因此堆会按升序排列，堆顶是最小值。

二、大顶堆与小顶堆的对比

特性	大顶堆（默认）	小顶堆（greater）
模板参数	priority_queue<int>	priority_queue<int, vector<int>, greater<int>>
堆顶元素	最大值	最小值
插入操作	保持堆顶为最大值	保持堆顶为最小值
应用场景	取最大值、任务调度（高优先级）	取最小值、最小生成树算法

三、小顶堆的常用操作示例

#include <iostream>
#include <queue>
#include <vector>int main() {// 创建小顶堆std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;// 插入元素minHeap.push(5);minHeap.push(1);minHeap.push(3);minHeap.push(2);minHeap.push(4);// 堆顶是最小值std::cout << "堆顶元素（最小值）: " << minHeap.top() << std::endl;  // 输出: 1// 弹出堆顶元素minHeap.pop();std::cout << "弹出后堆顶元素: " << minHeap.top() << std::endl;     // 输出: 2// 查看堆的大小std::cout << "堆大小: " << minHeap.size() << std::endl;            // 输出: 4// 注意：priority_queue不支持随机访问，只能通过弹出操作遍历while (!minHeap.empty()) {std::cout << minHeap.top() << " ";minHeap.pop();}// 输出: 2 3 4 5std::cout << std::endl;return 0;
}

四、在中位数查找中的应用

在LeetCode 295题中，小顶堆用于保存较大的一半数字，大顶堆保存较小的一半数字：

class MedianFinder {
private:std::priority_queue<int> maxHeap;          // 大顶堆，保存较小的一半std::priority_queue<int, vector<int>, greater<int>> minHeap;  // 小顶堆，保存较大的一半public:void addNum(int num) {if (maxHeap.empty() || num <= maxHeap.top()) {maxHeap.push(num);} else {minHeap.push(num);}// 调整堆大小平衡if (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();}}double findMedian() {if (maxHeap.size() > minHeap.size()) {return maxHeap.top();} else {return (maxHeap.top() + minHeap.top()) / 2.0;}}
};

• 小顶堆的作用：确保较大的一半数字按升序排列，堆顶是其中最小值。
• 大顶堆的作用：确保较小的一半数字按降序排列，堆顶是其中最大值。

五、greater<int>的底层实现

std::greater<int>是一个函数对象（仿函数），其operator()定义如下：

struct greater {bool operator()(const int& x, const int& y) const {return x > y;}
};

• 当x > y时返回true，因此在priority_queue中，较小的元素会被推到堆顶，形成小顶堆。

总结

• 小顶堆的实现：使用priority_queue<int, vector<int>, greater<int>>。
• 核心原理：通过greater<int>改变元素的比较方式，使堆顶始终为最小值。
• 应用场景：需要频繁获取最小值的场景，如优先队列、中位数查找、最小生成树算法等。

掌握小顶堆的实现和原理，能帮助你在算法题中高效解决需要维护有序数据的数据结构问题。

双堆实现中位数查找时堆平衡条件的解释

在使用双堆（大顶堆和小顶堆）实现中位数查找器时，堆平衡条件的设计是确保能正确获取中位数的关键。让我解释为什么在判断堆大小时，两个条件存在差异：

双堆实现的基本原理

在中位数查找器中，我们使用：

• 大顶堆 maxHeap 保存较小的一半数字
• 小顶堆 minHeap 保存较大的一半数字

为了确保能正确获取中位数，需要满足：

• 当总数字个数为奇数时，大顶堆的大小比小顶堆大1，此时大顶堆顶就是中位数
• 当总数字个数为偶数时，两个堆大小相等，此时中位数是两个堆顶的平均值

堆平衡条件分析

if (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();
}

为什么大顶堆的条件是 maxHeap.size() > minHeap.size() + 1？

• 大顶堆应该保存较小的一半数字，当总数字个数为奇数时，大顶堆大小应比小顶堆大1
• 当大顶堆的大小超过小顶堆大小1以上时（即maxHeap.size() >= minHeap.size() + 2），需要调整
• 例如：大顶堆有5个元素，小顶堆有3个元素，差值为2，需要调整

为什么小顶堆的条件是 minHeap.size() > maxHeap.size()？

• 当总数字个数为偶数时，两个堆大小应相等
• 当小顶堆的大小超过大顶堆时（即minHeap.size() >= maxHeap.size() + 1），需要调整
• 例如：小顶堆有4个元素，大顶堆有3个元素，差值为1，需要调整

关键差异的原因

大顶堆允许的最大差值是1，小顶堆不允许任何差值

• 大顶堆可以比小顶堆多1个元素（当总元素个数为奇数时）
• 小顶堆不能比大顶堆多元素，最多只能相等（当总元素个数为偶数时）

示例说明

假设当前大顶堆和小顶堆的大小分别为：

• 情况1：maxHeap.size() = 5, minHeap.size() = 3

  • 差值为2，满足maxHeap.size() > minHeap.size() + 1（5 > 3+1），需要调整
  • 调整后：maxHeap.size() = 4, minHeap.size() = 4

• 情况2：maxHeap.size() = 3, minHeap.size() = 4

  • 满足minHeap.size() > maxHeap.size()（4 > 3），需要调整
  • 调整后：maxHeap.size() = 4, minHeap.size() = 3

• 情况3：maxHeap.size() = 4, minHeap.size() = 3

  • 差值为1，满足奇数个元素的条件，无需调整
  • 中位数为大顶堆顶元素

• 情况4：maxHeap.size() = 3, minHeap.size() = 3

  • 满足偶数个元素的条件，无需调整
  • 中位数为两个堆顶元素的平均值

总结

堆平衡条件的设计基于以下原则：

1. 大顶堆可以比小顶堆多1个元素（奇数个元素时）
2. 小顶堆不能比大顶堆多元素，最多相等（偶数个元素时）
3. 当大顶堆大小超过小顶堆大小1以上时需要调整（+1的由来）
4. 当小顶堆大小超过大顶堆时需要调整（不需要+1，因为不允许小顶堆更大）

这种条件设计确保了：

• 大顶堆始终保存较小的一半数字
• 小顶堆始终保存较大的一半数字
• 可以在O(1)时间内获取中位数

理解这些条件背后的原理，有助于更好地掌握双堆数据结构在中位数查找中的应用。

你修改后的代码在每次插入新元素时立即排序，虽然简化了中位数查找的逻辑，但整体效率仍然不如双堆实现。这是因为排序操作的时间复杂度远高于堆操作。以下是详细分析：

一、时间复杂度对比

1. 你的修改版本

• 插入操作 addNum：
  每次插入后排序整个数组，时间复杂度为 O(n log n)，其中 n 是当前元素数量。
  （注：即使使用二分查找找到插入位置，移动元素的时间复杂度仍为 O(n)，整体仍为 O(n)。）

• 查询操作 findMedian：
  直接访问中间元素，时间复杂度为 O(1)。

2. 双堆实现

• 插入操作 addNum：
  维护两个堆的平衡，时间复杂度为 O(log n)。
  （堆的插入/删除操作时间为 O(log n)，调整平衡最多两次堆操作。）

• 查询操作 findMedian：
  直接访问堆顶元素，时间复杂度为 O(1)。

3. 性能差异

假设进行 m 次插入和查询，总时间复杂度：

• 你的实现：O(m × n log n)
  每次插入都需排序整个数组，n 随插入次数增长，最终接近 m。
• 双堆实现：O(m × log n)
  每次插入仅需对数时间维护堆平衡。

二、为什么排序效率低？

排序操作（如快速排序、归并排序）的时间复杂度为 O(n log n)，这在数据量大时非常昂贵。即使你每次插入后立即排序，避免了重复排序的开销，但单次排序的代价仍然远高于堆的对数时间操作。

三、示例对比

假设已有 10,000 个元素，插入第 10,001 个元素：

• 你的实现：
  对 10,001 个元素排序，需执行约 10,001 × log₂(10,001) ≈ 130,000 次操作。
• 双堆实现：
  调整两个堆的平衡，最多需执行 2 × log₂(10,001) ≈ 26 次操作。

随着数据量增长，排序的开销呈指数级上升，而堆操作始终保持对数时间。

四、优化方向：插入排序（仍不如双堆）

如果你希望保持数组有序，可以使用插入排序（二分查找定位插入位置），将插入时间优化到 O(n)：

class MedianFinder {
private:vector<int> nums;public:void addNum(int num) {// 二分查找插入位置auto it = lower_bound(nums.begin(), nums.end(), num);nums.insert(it, num);  // 插入操作 O(n)}double findMedian() {int n = nums.size();return n % 2 ? nums[n/2] : (nums[n/2] + nums[n/2-1]) / 2.0;}
};

但插入操作的 O(n) 仍劣于双堆的 O(log n)，尤其是在数据量大时。

五、双堆实现的核心优势

1. 动态维护有序性：
   堆结构通过 O(log n) 时间调整，始终保持堆顶元素为中位数的候选者。

2. 避免全局排序：
   不需要对所有元素排序，仅维护两个堆的局部有序性，节省大量计算资源。

3. 适用于流数据：
   每次插入和查询的时间复杂度稳定，即使处理海量数据流也能保持高效。

总结

你的修改版本虽然简化了代码逻辑，但每次插入后的排序操作成为性能瓶颈。双堆实现通过局部有序性和对数时间操作，在动态数据场景下显著优于全局排序方案。这体现了算法设计中数据结构选择的重要性——合适的数据结构（如堆）能将问题的时间复杂度从 O(n log n) 优化到 O(log n)。