每日算法一练：剑指offer——数组篇（4）

标签：大顶 maxHeap offer 元素中位数 addNum 算法数组 minHeap

数据流中的中位数

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

例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

示例 1：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

提示：

最多会对 addNum、findMedian 进行 50000 次调用。

解题思路

在这个问题中，我们需要支持两个操作：添加数字和找到当前数字的中位数。由于数据流是动态的，我们不能简单地对所有数字进行排序来找到中位数，因为这在性能上是不可行的，特别是在有大量数据时。

为了高效地维护中位数，我们可以使用 两个堆（大顶堆和小顶堆）的结构来管理数据：

大顶堆（Max Heap）：用来存储较小的一半元素。这样，堆顶的元素就是这部分元素中的最大值。
小顶堆（Min Heap）：用来存储较大的一半元素。这样，堆顶的元素就是这部分元素中的最小值。

核心思想

堆的大小关系：
- 大顶堆的大小可以比小顶堆多 1，或者两者大小相等。
- 这确保了我们可以快速找到中位数：
  - 如果大顶堆的大小大于小顶堆，当前中位数就是大顶堆的堆顶元素。
  - 如果两者大小相等，中位数是两个堆顶元素的平均值。

算法流程

以下是实现中位数查找的详细算法流程：

初始化：
- 创建一个大顶堆 maxHeap 用于存储较小的一半元素。
- 创建一个小顶堆 minHeap 用于存储较大的一半元素。
添加数字（addNum(int num) 方法）：
- 将新数字添加到大顶堆 maxHeap。
- 检查并保持堆的平衡性：
  - 如果 maxHeap 的堆顶元素大于 minHeap 的堆顶元素，则将 maxHeap 的堆顶元素移到 minHeap。
- 确保两个堆的大小关系：
  - 如果 maxHeap 的大小超过 minHeap 的大小 + 1，则将 maxHeap 的堆顶元素移到 minHeap。
  - 如果 minHeap 的大小超过 maxHeap，则将 minHeap 的堆顶元素移到 maxHeap。
查找中位数（findMedian() 方法）：
- 如果 maxHeap 的大小大于 minHeap，返回 maxHeap 的堆顶元素。
- 如果 maxHeap 和 minHeap 的大小相等，返回两个堆顶元素的平均值。

代码实现

import java.util.PriorityQueue; // 引入优先队列类

class MedianFinder {
    Queue<Integer> A, B; // 定义两个队列，A 为小顶堆，B 为大顶堆

    // 构造函数，初始化两个堆
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }

    // 添加数字
    public void addNum(int num) {
        // 判断当前两个堆的大小是否相等
        if (A.size() != B.size()) {
            // 如果不相等，将新数字添加到小顶堆 A
            A.add(num);
            // 将 A 的堆顶元素（当前最小的较大的一半）移到大顶堆 B
            B.add(A.poll());
        } else {
            // 如果相等，将新数字添加到大顶堆 B
            B.add(num);
            // 将 B 的堆顶元素（当前最大的较小的一半）移到小顶堆 A
            A.add(B.poll());
        }
    }

    // 查找中位数
    public double findMedian() {
        // 如果 A 的大小大于 B，则中位数为 A 的堆顶元素
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0; // 返回两个堆顶元素的平均值
    }
}

复杂度分析

时间复杂度：
- addNum(int num)：O(log N)，因为在堆中插入或移除元素的时间复杂度是对数级别。
- findMedian()：O(1)，因为我们直接访问堆顶元素。
空间复杂度：O(N)，因为我们需要存储所有输入的数字。

总结

本题旨在设计一个支持动态数据流中中位数计算的数据结构。我们通过使用两个堆（小顶堆和大顶堆）来实现这一目标。这种方法不仅能够高效地添加新数字，还能快速地找到当前的中位数。小顶堆用于存储较大的一半元素，而大顶堆用于存储较小的一半元素。通过维护这两个堆的大小关系，我们可以在 O(log N) 的时间复杂度内实现添加操作，同时在 O(1) 的时间复杂度内计算中位数。

具体而言，当新数字被添加时，我们会将其放入适当的堆中，并确保堆的大小关系正确，从而使得中位数可以从堆顶元素中快速获取。这种方法的优势在于能够处理大量的插入和查询操作，而不需要频繁地对整个数据集进行排序。

这种基于堆的数据结构不仅简洁高效，也展示了如何通过合理的设计在算法性能上实现优化，适用于需要动态更新的统计计算场景。

标签：大顶,maxHeap,offer,元素,中位数,addNum,算法,数组,minHeap
From： https://blog.csdn.net/m0_53926113/article/details/143179837