LeetCode经典算法面试题 #295：数据流的中位数（双堆法、有序列表、平衡树等多种实现方案详解）

1.问题描述

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

例如arr = [2,3,4]的中位数是3。
例如arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。

实现MedianFinder类：

• MedianFinder()初始化对象。
• void addNum(int num)将数据流中的整数num添加到数据结构中。
• double findMedian()返回到目前为止所有元素的中位数。

示例：

输入： ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出： [null, null, null, 1.5, null, 2.0] 解释： MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr = [1, 2, 3] medianFinder.findMedian(); // 返回 2.0

提示：

• -10^5 <= num <= 10^5
• 在调用findMedian之前，数据结构中至少有一个元素
• 最多5 × 10^4次调用addNum和findMedian

2.问题分析

2.1 题目理解

这是一个动态数据流中求中位数的问题。与静态数组不同，数据是不断增加的，每次添加一个数后，我们都需要能够快速（通常要求 O(log n) 或更优）得到当前所有数的中位数。

中位数将有序数组分成两个长度相等（或相差 1）的部分：左半部分的所有元素 ≤ 右半部分的所有元素。因此，我们可以维护两个堆来分别存储左半部分和右半部分，并保持大小平衡。

2.2 核心洞察

• 两堆平衡：将数据分为较小的一半和较大的一半，较小的一半用最大堆存储，较大的一半用最小堆存储。
• 堆的维护：每次插入时，根据元素大小决定放入哪个堆，然后调整两个堆的大小，使它们满足size_maxHeap >= size_minHeap且size_maxHeap - size_minHeap <= 1（或相反）。
• 中位数计算：
  • 当元素总数为奇数时，中位数是较大堆（或较小堆）的堆顶；
  • 当元素总数为偶数时，中位数是两个堆顶的平均值。
• 时间复杂度：每次插入 O(log n)，查询 O(1)。

2.3 破题关键

• 使用 Java 的PriorityQueue实现最大堆和最小堆。
• 注意堆的排序规则：最小堆用默认比较器，最大堆用(a, b) -> b - a或Collections.reverseOrder()。
• 平衡策略：确保最大堆的大小 ≥ 最小堆的大小，且差值 ≤ 1。通常做法是：先默认将元素插入最大堆，然后将最大堆的堆顶移入最小堆，再调整两个堆的大小。

3.算法设计与实现

3.1 解法一：双堆法（优先队列）

核心思想：

维护两个堆：最大堆（small）存放较小的一半，最小堆（large）存放较大的一半。始终保持small.size() >= large.size()且small.size() - large.size() <= 1。

算法思路：

1. addNum(num)：
   • 先将num插入small（最大堆）。
   • 将small的堆顶元素移到large（最小堆）中。
   • 如果small.size() < large.size()，将large的堆顶移回small。
2. findMedian()：
   • 如果总数为奇数（small.size() > large.size()），返回small.peek()。
   • 否则返回(small.peek() + large.peek()) / 2.0。

Java代码实现：

importjava.util.PriorityQueue;classMedianFinder{privatePriorityQueue<Integer>small;// 最大堆，存放较小的一半privatePriorityQueue<Integer>large;// 最小堆，存放较大的一半publicMedianFinder(){small=newPriorityQueue<>((a,b)->b-a);large=newPriorityQueue<>();}publicvoidaddNum(intnum){small.offer(num);large.offer(small.poll());// 保持 small 的大小 >= large 的大小if(small.size()<large.size()){small.offer(large.poll());}}publicdoublefindMedian(){if(small.size()>large.size()){returnsmall.peek();}else{return(small.peek()+large.peek())/2.0;}}}

性能分析：

• 时间复杂度：addNumO(log n)，findMedianO(1)
• 空间复杂度：O(n)，存储所有元素
• 优点：实现简单，每个操作都是对数时间
• 缺点：需要两个堆

3.2 解法二：有序列表（二分插入）

核心思想：

使用ArrayList存储所有元素，每次插入时通过二分查找找到插入位置，然后add插入。虽然插入是 O(n)，但实现简单，对于小规模数据（如本题 5×10^4）可能勉强可行，但并非最优。

算法思路：

1. addNum(num)：
   • 使用Collections.binarySearch找到插入位置。
   • 调用list.add(pos, num)插入。
2. findMedian()：
   • 直接根据列表大小返回中位数。

Java代码实现：

importjava.util.ArrayList;importjava.util.Collections;classMedianFinder{privateArrayList<Integer>list;publicMedianFinder(){list=newArrayList<>();}publicvoidaddNum(intnum){intpos=Collections.binarySearch(list,num);if(pos<0)pos=-pos-1;list.add(pos,num);}publicdoublefindMedian(){intn=list.size();if(n%2==1){returnlist.get(n/2);}else{return(list.get(n/2-1)+list.get(n/2))/2.0;}}}

性能分析：

• 时间复杂度：addNumO(n)，findMedianO(1)
• 空间复杂度：O(n)
• 优点：实现直观
• 缺点：插入效率低，不满足对数要求

3.3 解法三：平衡二叉搜索树（TreeSet 模拟）

核心思想：

Java 的TreeSet基于红黑树实现，但默认不允许重复元素。为了处理重复，我们可以存储自定义对象（元素值和插入顺序），并维护一个指针来快速访问中位数。但获取第 k 个元素需要遍历，复杂度 O(k)，实际不可行。这里展示一种使用TreeSet并配合迭代器的方法，但仅作为思路参考。

算法思路：

1. 使用TreeSet<Pair>存储元素，Pair包含值和序号。
2. 维护一个迭代器指向中位数位置。
3. 插入时，根据位置调整迭代器。

Java代码实现（简化，仅演示）：

importjava.util.TreeSet;classMedianFinder{privateTreeSet<Pair>set;privateintcount;privatePairmedianLeft,medianRight;// 用于快速访问privatestaticclassPairimplementsComparable<Pair>{intvalue;intid;Pair(intvalue,intid){this.value=value;this.id=id;}@OverridepublicintcompareTo(Pairo){if(this.value!=o.value)returnInteger.compare(this.value,o.value);returnInteger.compare(this.id,o.id);}}publicMedianFinder(){set=newTreeSet<>();count=0;medianLeft=medianRight=null;}publicvoidaddNum(intnum){Pairp=newPair(num,count++);set.add(p);// 更新中位数指针，逻辑复杂，这里省略// 需要维护两个指针指向中间位置，插入后可能需要移动}publicdoublefindMedian(){// 需要正确维护 medianLeft 和 medianRight// 实际实现复杂，此处仅示意return0.0;}}

说明：由于实现复杂且性能不如双堆，实际中不推荐使用。

3.4 解法四：基于数组的插入排序

核心思想：

使用数组存储元素，每次插入时找到合适位置并移动元素。本质是插入排序，效率低。

Java代码实现：

importjava.util.Arrays;classMedianFinder{privateint[]arr;privateintsize;publicMedianFinder(){arr=newint[50000];// 预分配最大容量size=0;}publicvoidaddNum(intnum){intpos=0;while(pos<size&&arr[pos]<num)pos++;// 移动元素System.arraycopy(arr,pos,arr,pos+1,size-pos);arr[pos]=num;size++;}publicdoublefindMedian(){if(size%2==1){returnarr[size/2];}else{return(arr[size/2-1]+arr[size/2])/2.0;}}}

性能分析：

• 时间复杂度：addNumO(n)，findMedianO(1)
• 空间复杂度：O(n)
• 优点：简单
• 缺点：插入效率低

3.5 解法五：支持删除操作的动态中位数（懒删除 + 双堆）

核心思想：

在双堆基础上增加一个HashMap记录待删除的元素，当堆顶元素需要被删除时，延迟删除并调整堆。这种结构支持删除任意元素（需要知道元素值），但题目未要求删除，此处作为扩展。

算法思路：

• 维护small（最大堆）和large（最小堆）以及一个Map记录待删除元素的计数。
• addNum(num)同双堆法，但需要平衡时清理堆顶的待删除元素。
• removeNum(num)将num加入待删除映射，然后触发平衡。
• findMedian()前清理堆顶。

Java代码实现：

importjava.util.PriorityQueue;importjava.util.HashMap;importjava.util.Map;classMedianFinderWithDelete{privatePriorityQueue<Integer>small;// 最大堆privatePriorityQueue<Integer>large;// 最小堆privateMap<Integer,Integer>toRemove;// 待删除计数privateintsmallSize,largeSize;// 实际大小（不含待删除）publicMedianFinderWithDelete(){small=newPriorityQueue<>((a,b)->b-a);large=newPriorityQueue<>();toRemove=newHashMap<>();smallSize=largeSize=0;}publicvoidaddNum(intnum){if(small.isEmpty()||num<=small.peek()){small.offer(num);smallSize++;}else{large.offer(num);largeSize++;}balance();}publicvoidremoveNum(intnum){toRemove.put(num,toRemove.getOrDefault(num,0)+1);// 如果堆顶正好是要删除的元素，需要延迟清理if(!small.isEmpty()&&small.peek()==num){prune(small);smallSize--;}elseif(!large.isEmpty()&&large.peek()==num){prune(large);largeSize--;}else{// 不在堆顶，只减少计数，不立即删除if(num<=small.peek())smallSize--;elselargeSize--;}balance();}privatevoidprune(PriorityQueue<Integer>heap){while(!heap.isEmpty()&&toRemove.getOrDefault(heap.peek(),0)>0){inttop=heap.poll();toRemove.put(top,toRemove.get(top)-1);if(toRemove.get(top)==0)toRemove.remove(top);}}privatevoidbalance(){if(smallSize>largeSize+1){large.offer(small.poll());smallSize--;largeSize++;prune(small);}elseif(largeSize>smallSize){small.offer(large.poll());smallSize++;largeSize--;prune(large);}// 清理可能出现在堆顶的待删除元素prune(small);prune(large);}publicdoublefindMedian(){if(smallSize>largeSize){returnsmall.peek();}else{return(small.peek()+large.peek())/2.0;}}}

性能分析：

• 时间复杂度：addNumO(log n)，removeNumO(log n)（分摊），findMedianO(1)
• 空间复杂度：O(n)
• 优点：支持删除操作
• 缺点：实现复杂，需要维护待删除映射

4.性能对比

4.1 理论复杂度对比表

4.2 实际性能测试（估算）

对于 5×10^4 次插入：

• 双堆法：约 5×10^4 × log(5×10^4) ≈ 8×10^5 次操作，很快。
• 有序列表：最坏 O(n²) ≈ 2.5×10^9，不可接受。

4.3 各场景适用性分析

• 面试场景：双堆法是标准答案，必须掌握。
• 实际生产：双堆法足够。
• 需要删除操作：懒删除双堆法。

5.扩展与变体

5.1 变体一：滑动窗口的中位数

题目描述：给定一个数组和一个整数 k，求所有长度为 k 的连续子数组的中位数。

思路：使用双堆 + 延迟删除，维护一个滑动窗口。

Java代码实现：

importjava.util.*;classSlidingWindowMedian{publicdouble[]medianSlidingWindow(int[]nums,intk){intn=nums.length;double[]result=newdouble[n-k+1];MedianFinderWithDeletemf=newMedianFinderWithDelete();for(inti=0;i<n;i++){mf.addNum(nums[i]);if(i>=k){mf.removeNum(nums[i-k]);}if(i>=k-1){result[i-k+1]=mf.findMedian();}}returnresult;}}

（注：此处使用前面实现的MedianFinderWithDelete类）

5.2 变体二：数据流中的第K大元素

题目描述：设计一个类，从数据流中接收元素，并能随时返回当前第 k 大的元素。

Java代码实现：

importjava.util.PriorityQueue;classKthLargest{privatePriorityQueue<Integer>minHeap;privateintk;publicKthLargest(intk,int[]nums){this.k=k;minHeap=newPriorityQueue<>(k);for(intnum:nums){add(num);}}publicintadd(intval){if(minHeap.size()<k){minHeap.offer(val);}elseif(val>minHeap.peek()){minHeap.poll();minHeap.offer(val);}returnminHeap.peek();}}

5.3 变体三：数据流中的众数

题目描述：实时返回数据流中出现次数最多的元素（若有多个返回任意一个）。

Java代码实现：

importjava.util.*;classMajorityFinder{privateMap<Integer,Integer>freq;privatePriorityQueue<Map.Entry<Integer,Integer>>maxHeap;publicMajorityFinder(){freq=newHashMap<>();maxHeap=newPriorityQueue<>((a,b)->b.getValue()-a.getValue());}publicvoidadd(intnum){freq.put(num,freq.getOrDefault(num,0)+1);// 更新堆：懒删除，每次查询时重建或使用更高效方法// 为简单，每次查询时重建堆}publicintgetMajority(){// 重建堆（实际效率低，仅示意）maxHeap.clear();for(Map.Entry<Integer,Integer>e:freq.entrySet()){maxHeap.offer(e);}returnmaxHeap.peek().getKey();}}

更高效方法：使用HashMap和TreeMap按频率排序，但实现复杂。

5.4 变体四：支持删除的动态中位数

题目描述：在双堆基础上增加删除操作（见 3.5 解法五）。

6.总结

6.1 核心思想总结

• 使用两个堆（最大堆和最小堆）分别存储较小的一半和较大的一半。
• 保持两个堆的大小平衡，使得中位数可以通过堆顶元素直接计算。
• 每个插入操作 O(log n)，查询 O(1)。

6.2 实际应用场景

• 实时统计系统指标（如响应时间的中位数）
• 金融领域中的移动平均线
• 科学计算中的在线分位数估计

6.3 面试建议

• 重点掌握双堆法，并能手写代码。
• 解释为什么用最大堆和最小堆。
• 分析时间复杂度和平衡策略。
• 可以提及更复杂的变体（如支持删除）。

6.4 常见面试问题Q&A

Q1：为什么需要两个堆？
A1：因为中位数需要将数据分成左右两部分，两个堆分别维护这两部分，且能快速获取左右的最大值和最小值。

Q2：如何保证两个堆的大小平衡？
A2：通过每次插入后调整，确保size_maxHeap >= size_minHeap且差值 ≤ 1。常见的调整方式：先插入最大堆，再移一个到最小堆，再根据大小调整。

Q3：如果有大量重复元素，堆法有效吗？
A3：有效，因为堆只比较元素值，重复元素会被正常处理。

Q4：能否用一个堆实现？
A4：不能，因为一个堆无法同时获取最大值和最小值，也无法确定中位数位置。

Q5：数据流的中位数可以扩展到多个数据流吗？
A5：可以，但需要更复杂的数据结构，如对顶堆的扩展或使用平衡树。