小学生都能看懂的题解 | #数据流中的中位数#

问题是什么？

我们需要一个程序，这个程序可以从一个数据流里不断地读取数字，并且能随时告诉我们这些数字的“中间数”（也就是中位数）。如果数字的总数是奇数，中位数就是正中间的那个数；如果是偶数，中位数就是中间两个数的平均值。

我们怎么解决？

我们可以想象有两个队伍，一个是“小队”，一个是“大队”。每次新来一个数字，我们就把它放到合适的队伍里。“小队”总是放更小的数，“大队”放更大的数。但是，这两个队伍的人数不能差太多，最多只能差一个人。

具体怎么做？

1. 创建两个队伍：
1. “小队”用一个叫做 maxHeap 的特殊队伍，它总是让最大的数站在最前面。
2. “大队”用一个叫做 minHeap 的特殊队伍，它总是让最小的数站在最前面。
2. 每次有新数字来的时候：
1. 如果这个数字比“小队”的队长还小，或者“小队”是空的，就把它加到“小队”里。
2. 否则，把它加到“大队”里。
3. 保持队伍人数接近：
1. 如果“小队”的人数比“大队”多两个人以上，就把“小队”的队长送到“大队”去。
2. 如果“大队”的人数比“小队”多，就把“大队”的队长送到“小队”去。
4. 找出中位数：
1. 如果两个队伍人数一样，中位数就是两个队长的平均值。
2. 如果“小队”的人数比“大队”多一个，中位数就是“小队”的队长。

实现代码：

下面的代码实现了上面说的功能，使用了 Java 的 PriorityQueue（优先队列），来帮助我们管理这两个特殊的队伍。

import java.util.PriorityQueue;

public class MedianFinder {
    private PriorityQueue<Integer> smallTeam; // 小队，保存较小的数
    private PriorityQueue<Integer> bigTeam; // 大队，保存较大的数

    public MedianFinder() {
        smallTeam = new PriorityQueue<>((a, b) -> b - a); // 小队，让大的数排前面
        bigTeam = new PriorityQueue<>(); // 大队，让小的数排前面
    }

    // 插入新数字的方法
    public void Insert(Integer val) {
        if (smallTeam.isEmpty() || val <= smallTeam.peek()) {
            smallTeam.add(val);
        } else {
            bigTeam.add(val);
        }

        // 保持队伍人数接近
        if (smallTeam.size() > bigTeam.size() + 1) {
            bigTeam.add(smallTeam.poll());
        } else if (bigTeam.size() > smallTeam.size()) {
            smallTeam.add(bigTeam.poll());
        }
    }

    // 获取中位数的方法
    public Double GetMedian() {
        if (smallTeam.size() == bigTeam.size()) {
            return (smallTeam.peek() + bigTeam.peek()) / 2.0;
        } else {
            return (double)smallTeam.peek();
        }
    }
}

这个代码会把新来的数字放进合适的队伍，并且随时调整队伍，确保我们总能找到正确的中位数。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。