如何玩转数据流

MrHe··3 min read

今天聊一个在面试里出镜率极高，也特别能体现算法思维的话题——数据流。

啥是数据流？你可以想象成一个永无止境的传送带，上面源源不断地送来数据。比如，服务器的访问日志、股票市场的实时报价、传感器传回的温度读数。这些数据的特点是：

  1. 量巨大，甚至可能是无限的。

  2. 你没法一次性拿到所有数据，它们是一个一个来的。

  3. 内存有限，你不可能把所有数据都存下来。

处理这种问题的算法，就叫数据流算法。它考验的是我们如何在有限的资源下，做到快速响应和计算。

今天，咱们就拿数据流里最经典的一道题开刀：数据流中的中位数。

题目描述： 设计一个数据结构，支持以下两种操作：

  1. void addNum(int num) - 从数据流中添加一个整数到数据结构中。

  2. double findMedian() - 返回目前所有元素的中位数。

我们先明确一下啥是中位数。如果数据个数是奇数，中位数就是排序后最中间的那个数。如果是偶数，就是排序后最中间两个数的平均值。

比如，[2, 3, 4] 的中位数是 3。[2, 3, 4, 5] 的中位数是 (3 + 4) / 2 = 3.5。

拿到这个题，我的第一反应是啥？先不想那些花里胡哨的，就用最暴力、最直接的办法搞定它。

解法一：暴力美学，每次都排序

最无脑的思路是啥？我管你什么数据流，来一个数，我就存一个。用什么存？ArrayList 啊，简单方便。

  • addNum(int num)：直接把 num 加到 ArrayList 的末尾。这操作，时间复杂度 O(1)。

  • findMedian()：要找中位数，前提是数据有序。那好办，我直接对整个 ArrayList 调用 Collections.sort()，排完序再根据奇偶数取中间值。排序的复杂度是 O(N log N)，取值的复杂度是 O(1)。所以总的 findMedian 复杂度是 O(N log N)。

这个思路简单直接，代码也好写。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class MedianFinderV1 {
    private List<Integer> list;

    public MedianFinderV1() {
        list = new ArrayList<>();
    }

    public void addNum(int num) {
        list.add(num);
    }

    public double findMedian() {
        // 核心操作：每次都完整排序
        Collections.sort(list);

        int n = list.size();
        if (n % 2 == 1) {
            return list.get(n / 2);
        } else {
            return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
        }
    }
}

这写法，面试官看了估计会点点头，然后问你：“如果数据流非常大，addNum 和 findMedian 会被频繁调用，你这个 O(N log N) 的 findMedian 能接受吗？”

肯定不能啊！每次 findMedian 都把所有数重新排一遍，这不傻吗？大量的工作都是重复的。比如，我已经有 100 万个数了，你再加一个数，我为了找中位数，又要把这 100 万零一个数从头到尾排一遍？性能瓶颈太明显了。

OK，思路升级。

解法二：保持有序，插入排序的思路

既然瓶颈在于反复的全局排序，那我们能不能在添加数据的时候就让它有序？这样 findMedian 不就 O(1) 了吗？

这个思路很自然。每次 addNum，我们不直接加到末尾，而是找到它应该在的排序位置，把它插进去。这不就是插入排序的核心思想嘛。

  • addNum(int num)：用二分查找在 ArrayList 中找到 num 合适的插入位置（O(log N)），然后执行插入操作。ArrayList 的插入操作需要移动后续所有元素，所以时间复杂度是 O(N)。

  • findMedian()：因为列表始终有序，直接取中间的数，时间复杂度 O(1)。

我们把复杂度从 findMedian 转移到了 addNum。

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

class MedianFinderV2 {
    private List<Integer> list;

    public MedianFinderV2() {
        list = new ArrayList<>();
    }

    public void addNum(int num) {
        // 使用二分查找找到插入点
        int index = Collections.binarySearch(list, num);
        if (index < 0) {
            // binarySearch没找到会返回 (-(insertion point) - 1)
            index = -index - 1;
        }
        list.add(index, num);
    }

    public double findMedian() {
        int n = list.size();
        if (n == 0) return 0; // 考虑边界情况

        if (n % 2 == 1) {
            return list.get(n / 2);
        } else {
            return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
        }
    }
}

这个解法比上一个好点了吗？表面上看，是的。findMedian 变得飞快。但 addNum 的 O(N) 复杂度在大数据量下依然是致命的。如果 addNum 调用 100 万次，findMedian 只调用几次，那这个方案简直是灾难。

两种方案，一个 addNum 快，findMedian 慢；另一个 addNum 慢，findMedian 快。总有一个操作是 O(N) 或 O(N log N) 级别的，都不够好。

核心问题在哪？

我们为了找到中位数，是不是真的需要维护一个完全有序的列表？其实并不需要。我们只关心中间那一个或两个数。整个数组的其他部分，我们只需要知道它们是 “比中位数小” 还是 “比中位数大” 就行了，至于它们内部的顺序，我们根本不关心。

这个想法，就是通往最优解的钥匙。

解法三：对半劈开，双堆结构的神奇魔法

既然我们只关心中间，那我们可以把所有数据分成两部分：

  1. 左半部分（较小的一半）

  2. 右半部分（较大的一半）

如果我们能做到：

  • 左半部分所有的数都小于等于右半部分所有的数。

  • 左半部分的数量和右半部分的数量保持平衡（最多差 1）。

那么中位数不就手到擒来了吗？

  • 如果总数是奇数，那个多出来的数就是中位数。

  • 如果总数是偶数，那中位数就是左半部分的最大值和右半部分的最小值的平均数。

现在的问题变成了：用什么数据结构来维护这两部分数据，并且能高效地拿到“左半部分的最大值”和“右半部分的最小值”？

答案呼之欲出：堆（Heap）！

  • 用一个 大顶堆（Max Heap） 来存左半部分的数据。这样堆顶永远是左半部分的最大值。

  • 用一个 小顶堆（Min Heap） 来存右半部分的数据。这样堆顶永远是右半部分的最小值。

我们来设计一下 addNum 的流程：

为了维持平衡，我们规定：大顶堆的大小要么等于小顶堆，要么比小顶堆多一个。

当一个新的数 num 来了之后：

  1. 先把它扔进大顶堆（存左半部分的那个）。

  2. 此时，大顶堆里可能放了一个“本该属于右半部分的大数”。怎么办？把大顶堆的堆顶元素（当前左半部分的最大值）弹出来，扔进小顶堆。

  3. 经过前两步，我们保证了“左边的都比右边的小”这个性质，但大小平衡可能被打破了。如果此时大顶堆的元素个数比小顶堆少了（比如，maxHeap.size() < minHeap.size()），说明小顶堆里有个元素本该是属于左半边的。那就从小顶堆弹出堆顶（右半部分的最小值），把它扔回大顶堆。

这样一套操作下来，两个堆的性质和大小平衡就都维持住了。

findMedian 怎么做？

  • 如果两个堆大小相等，说明总数是偶数，中位数就是 (大顶堆顶 + 小顶堆顶) / 2。

  • 如果大顶堆比小顶堆多一个，说明总数是奇数，中位数就是 大顶堆顶。

分析一下复杂度：

  • addNum：涉及 2-3 次堆的插入和弹出操作，每次操作都是 O(log N)。所以 addNum 的总复杂度是 O(log N)。

  • findMedian: 只需要看两个堆的堆顶，O(1)。

这个效率，简直是质的飞跃！

来看代码实现。Java 的 PriorityQueue 默认是小顶堆，要实现大顶堆，需要传入一个自定义的比较器。

import java.util.PriorityQueue;
import java.util.Collections;

class MedianFinderV3 {
    // 大顶堆，存放较小的一半数字
    private PriorityQueue<Integer> maxHeap;
    // 小顶堆，存放较大的一半数字
    private PriorityQueue<Integer> minHeap;

    public MedianFinderV3() {
        // (a, b) -> b - a  或者 Collections.reverseOrder() 都可以创建大顶堆
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // 1. 先把新数字加入大顶堆
        maxHeap.offer(num);

        // 2. 把大顶堆的最大元素（刚加进去的可能就是）移动到小顶堆
        minHeap.offer(maxHeap.poll());

        // 3. 维持平衡：如果大顶堆的元素少了，就从小顶堆“借”一个回来
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            // 总数为奇数，中位数在大顶堆的堆顶
            return maxHeap.peek();
        } else {
            // 总数为偶数，中位数是两个堆顶的平均值
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}

总结一下

你看，从一个简单的问题出发，我们的思维路径是这样的：

  1. 暴力解法 (V1)：先完成功能，不考虑效率。每次都全量排序，findMedian 是 O(N log N)。这能帮你理解问题，但肯定不是面试官想要的。

  2. 优化瓶颈 (V2)：发现反复排序是性能杀手。于是想到，能不能在插入时就维护好顺序？addNum 变为 O(N)，findMedian 优化到 O(1)。这是一种思路转换，把压力从一个操作转移到另一个操作，但总有短板。

  3. 重新审视问题 (V3)：跳出“必须完整排序”的思维定式。我们真的需要完整有序吗？不，我们只关心中间位置。这个思考触发了“对半分割”的想法，进而找到了最适合这个场景的数据结构——堆。最终，用双堆结构把 addNum 降到 O(log N)，findMedian 降到 O(1)，达到了非常理想的平衡。

  • #5pww5o2u5rwb