目录1.问题描述2.问题分析2.1 题目理解2.2 核心洞察2.3 破题关键3.算法设计与实现3.1 解法一双堆法优先队列3.2 解法二有序列表二分插入3.3 解法三平衡二叉搜索树TreeSet 模拟3.4 解法四基于数组的插入排序3.5 解法五支持删除操作的动态中位数懒删除 双堆4.性能对比4.1 理论复杂度对比表4.2 实际性能测试估算4.3 各场景适用性分析5.扩展与变体5.1 变体一滑动窗口的中位数5.2 变体二数据流中的第K大元素5.3 变体三数据流中的众数5.4 变体四支持删除的动态中位数6.总结6.1 核心思想总结6.2 实际应用场景6.3 面试建议6.4 常见面试问题QA1.问题描述中位数是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。例如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和findMedian2.问题分析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。算法思路addNum(num)先将num插入small最大堆。将small的堆顶元素移到large最小堆中。如果small.size() large.size()将large的堆顶移回small。findMedian()如果总数为奇数small.size() large.size()返回small.peek()。否则返回(small.peek() large.peek()) / 2.0。Java代码实现importjava.util.PriorityQueue;classMedianFinder{privatePriorityQueueIntegersmall;// 最大堆存放较小的一半privatePriorityQueueIntegerlarge;// 最小堆存放较大的一半publicMedianFinder(){smallnewPriorityQueue((a,b)-b-a);largenewPriorityQueue();}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可能勉强可行但并非最优。算法思路addNum(num)使用Collections.binarySearch找到插入位置。调用list.add(pos, num)插入。findMedian()直接根据列表大小返回中位数。Java代码实现importjava.util.ArrayList;importjava.util.Collections;classMedianFinder{privateArrayListIntegerlist;publicMedianFinder(){listnewArrayList();}publicvoidaddNum(intnum){intposCollections.binarySearch(list,num);if(pos0)pos-pos-1;list.add(pos,num);}publicdoublefindMedian(){intnlist.size();if(n%21){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并配合迭代器的方法但仅作为思路参考。算法思路使用TreeSetPair存储元素Pair包含值和序号。维护一个迭代器指向中位数位置。插入时根据位置调整迭代器。Java代码实现简化仅演示importjava.util.TreeSet;classMedianFinder{privateTreeSetPairset;privateintcount;privatePairmedianLeft,medianRight;// 用于快速访问privatestaticclassPairimplementsComparablePair{intvalue;intid;Pair(intvalue,intid){this.valuevalue;this.idid;}OverridepublicintcompareTo(Pairo){if(this.value!o.value)returnInteger.compare(this.value,o.value);returnInteger.compare(this.id,o.id);}}publicMedianFinder(){setnewTreeSet();count0;medianLeftmedianRightnull;}publicvoidaddNum(intnum){PairpnewPair(num,count);set.add(p);// 更新中位数指针逻辑复杂这里省略// 需要维护两个指针指向中间位置插入后可能需要移动}publicdoublefindMedian(){// 需要正确维护 medianLeft 和 medianRight// 实际实现复杂此处仅示意return0.0;}}说明由于实现复杂且性能不如双堆实际中不推荐使用。3.4 解法四基于数组的插入排序核心思想使用数组存储元素每次插入时找到合适位置并移动元素。本质是插入排序效率低。Java代码实现importjava.util.Arrays;classMedianFinder{privateint[]arr;privateintsize;publicMedianFinder(){arrnewint[50000];// 预分配最大容量size0;}publicvoidaddNum(intnum){intpos0;while(possizearr[pos]num)pos;// 移动元素System.arraycopy(arr,pos,arr,pos1,size-pos);arr[pos]num;size;}publicdoublefindMedian(){if(size%21){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{privatePriorityQueueIntegersmall;// 最大堆privatePriorityQueueIntegerlarge;// 最小堆privateMapInteger,IntegertoRemove;// 待删除计数privateintsmallSize,largeSize;// 实际大小不含待删除publicMedianFinderWithDelete(){smallnewPriorityQueue((a,b)-b-a);largenewPriorityQueue();toRemovenewHashMap();smallSizelargeSize0;}publicvoidaddNum(intnum){if(small.isEmpty()||numsmall.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(numsmall.peek())smallSize--;elselargeSize--;}balance();}privatevoidprune(PriorityQueueIntegerheap){while(!heap.isEmpty()toRemove.getOrDefault(heap.peek(),0)0){inttopheap.poll();toRemove.put(top,toRemove.get(top)-1);if(toRemove.get(top)0)toRemove.remove(top);}}privatevoidbalance(){if(smallSizelargeSize1){large.offer(small.poll());smallSize--;largeSize;prune(small);}elseif(largeSizesmallSize){small.offer(large.poll());smallSize;largeSize--;prune(large);}// 清理可能出现在堆顶的待删除元素prune(small);prune(large);}publicdoublefindMedian(){if(smallSizelargeSize){returnsmall.peek();}else{return(small.peek()large.peek())/2.0;}}}性能分析时间复杂度addNumO(log n)removeNumO(log n)分摊findMedianO(1)空间复杂度O(n)优点支持删除操作缺点实现复杂需要维护待删除映射4.性能对比4.1 理论复杂度对比表解法addNum 时间复杂度findMedian 时间复杂度空间复杂度优点缺点双堆法O(log n)O(1)O(n)高效常用需维护两个堆有序列表O(n)O(1)O(n)简单插入慢平衡树O(log n)O(log n)O(n)通用实现复杂插入排序O(n)O(1)O(n)简单插入慢懒删除双堆O(log n)O(1)O(n)支持删除实现复杂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){intnnums.length;double[]resultnewdouble[n-k1];MedianFinderWithDeletemfnewMedianFinderWithDelete();for(inti0;in;i){mf.addNum(nums[i]);if(ik){mf.removeNum(nums[i-k]);}if(ik-1){result[i-k1]mf.findMedian();}}returnresult;}}注此处使用前面实现的MedianFinderWithDelete类5.2 变体二数据流中的第K大元素题目描述设计一个类从数据流中接收元素并能随时返回当前第 k 大的元素。Java代码实现importjava.util.PriorityQueue;classKthLargest{privatePriorityQueueIntegerminHeap;privateintk;publicKthLargest(intk,int[]nums){this.kk;minHeapnewPriorityQueue(k);for(intnum:nums){add(num);}}publicintadd(intval){if(minHeap.size()k){minHeap.offer(val);}elseif(valminHeap.peek()){minHeap.poll();minHeap.offer(val);}returnminHeap.peek();}}5.3 变体三数据流中的众数题目描述实时返回数据流中出现次数最多的元素若有多个返回任意一个。Java代码实现importjava.util.*;classMajorityFinder{privateMapInteger,Integerfreq;privatePriorityQueueMap.EntryInteger,IntegermaxHeap;publicMajorityFinder(){freqnewHashMap();maxHeapnewPriorityQueue((a,b)-b.getValue()-a.getValue());}publicvoidadd(intnum){freq.put(num,freq.getOrDefault(num,0)1);// 更新堆懒删除每次查询时重建或使用更高效方法// 为简单每次查询时重建堆}publicintgetMajority(){// 重建堆实际效率低仅示意maxHeap.clear();for(Map.EntryInteger,Integere: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 常见面试问题QAQ1为什么需要两个堆A1因为中位数需要将数据分成左右两部分两个堆分别维护这两部分且能快速获取左右的最大值和最小值。Q2如何保证两个堆的大小平衡A2通过每次插入后调整确保size_maxHeap size_minHeap且差值 ≤ 1。常见的调整方式先插入最大堆再移一个到最小堆再根据大小调整。Q3如果有大量重复元素堆法有效吗A3有效因为堆只比较元素值重复元素会被正常处理。Q4能否用一个堆实现A4不能因为一个堆无法同时获取最大值和最小值也无法确定中位数位置。Q5数据流的中位数可以扩展到多个数据流吗A5可以但需要更复杂的数据结构如对顶堆的扩展或使用平衡树。
LeetCode经典算法面试题 #295：数据流的中位数（双堆法、有序列表、平衡树等多种实现方案详解）
发布时间：2026/6/1 12:56:11
目录1.问题描述2.问题分析2.1 题目理解2.2 核心洞察2.3 破题关键3.算法设计与实现3.1 解法一双堆法优先队列3.2 解法二有序列表二分插入3.3 解法三平衡二叉搜索树TreeSet 模拟3.4 解法四基于数组的插入排序3.5 解法五支持删除操作的动态中位数懒删除 双堆4.性能对比4.1 理论复杂度对比表4.2 实际性能测试估算4.3 各场景适用性分析5.扩展与变体5.1 变体一滑动窗口的中位数5.2 变体二数据流中的第K大元素5.3 变体三数据流中的众数5.4 变体四支持删除的动态中位数6.总结6.1 核心思想总结6.2 实际应用场景6.3 面试建议6.4 常见面试问题QA1.问题描述中位数是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。例如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和findMedian2.问题分析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。算法思路addNum(num)先将num插入small最大堆。将small的堆顶元素移到large最小堆中。如果small.size() large.size()将large的堆顶移回small。findMedian()如果总数为奇数small.size() large.size()返回small.peek()。否则返回(small.peek() large.peek()) / 2.0。Java代码实现importjava.util.PriorityQueue;classMedianFinder{privatePriorityQueueIntegersmall;// 最大堆存放较小的一半privatePriorityQueueIntegerlarge;// 最小堆存放较大的一半publicMedianFinder(){smallnewPriorityQueue((a,b)-b-a);largenewPriorityQueue();}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可能勉强可行但并非最优。算法思路addNum(num)使用Collections.binarySearch找到插入位置。调用list.add(pos, num)插入。findMedian()直接根据列表大小返回中位数。Java代码实现importjava.util.ArrayList;importjava.util.Collections;classMedianFinder{privateArrayListIntegerlist;publicMedianFinder(){listnewArrayList();}publicvoidaddNum(intnum){intposCollections.binarySearch(list,num);if(pos0)pos-pos-1;list.add(pos,num);}publicdoublefindMedian(){intnlist.size();if(n%21){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并配合迭代器的方法但仅作为思路参考。算法思路使用TreeSetPair存储元素Pair包含值和序号。维护一个迭代器指向中位数位置。插入时根据位置调整迭代器。Java代码实现简化仅演示importjava.util.TreeSet;classMedianFinder{privateTreeSetPairset;privateintcount;privatePairmedianLeft,medianRight;// 用于快速访问privatestaticclassPairimplementsComparablePair{intvalue;intid;Pair(intvalue,intid){this.valuevalue;this.idid;}OverridepublicintcompareTo(Pairo){if(this.value!o.value)returnInteger.compare(this.value,o.value);returnInteger.compare(this.id,o.id);}}publicMedianFinder(){setnewTreeSet();count0;medianLeftmedianRightnull;}publicvoidaddNum(intnum){PairpnewPair(num,count);set.add(p);// 更新中位数指针逻辑复杂这里省略// 需要维护两个指针指向中间位置插入后可能需要移动}publicdoublefindMedian(){// 需要正确维护 medianLeft 和 medianRight// 实际实现复杂此处仅示意return0.0;}}说明由于实现复杂且性能不如双堆实际中不推荐使用。3.4 解法四基于数组的插入排序核心思想使用数组存储元素每次插入时找到合适位置并移动元素。本质是插入排序效率低。Java代码实现importjava.util.Arrays;classMedianFinder{privateint[]arr;privateintsize;publicMedianFinder(){arrnewint[50000];// 预分配最大容量size0;}publicvoidaddNum(intnum){intpos0;while(possizearr[pos]num)pos;// 移动元素System.arraycopy(arr,pos,arr,pos1,size-pos);arr[pos]num;size;}publicdoublefindMedian(){if(size%21){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{privatePriorityQueueIntegersmall;// 最大堆privatePriorityQueueIntegerlarge;// 最小堆privateMapInteger,IntegertoRemove;// 待删除计数privateintsmallSize,largeSize;// 实际大小不含待删除publicMedianFinderWithDelete(){smallnewPriorityQueue((a,b)-b-a);largenewPriorityQueue();toRemovenewHashMap();smallSizelargeSize0;}publicvoidaddNum(intnum){if(small.isEmpty()||numsmall.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(numsmall.peek())smallSize--;elselargeSize--;}balance();}privatevoidprune(PriorityQueueIntegerheap){while(!heap.isEmpty()toRemove.getOrDefault(heap.peek(),0)0){inttopheap.poll();toRemove.put(top,toRemove.get(top)-1);if(toRemove.get(top)0)toRemove.remove(top);}}privatevoidbalance(){if(smallSizelargeSize1){large.offer(small.poll());smallSize--;largeSize;prune(small);}elseif(largeSizesmallSize){small.offer(large.poll());smallSize;largeSize--;prune(large);}// 清理可能出现在堆顶的待删除元素prune(small);prune(large);}publicdoublefindMedian(){if(smallSizelargeSize){returnsmall.peek();}else{return(small.peek()large.peek())/2.0;}}}性能分析时间复杂度addNumO(log n)removeNumO(log n)分摊findMedianO(1)空间复杂度O(n)优点支持删除操作缺点实现复杂需要维护待删除映射4.性能对比4.1 理论复杂度对比表解法addNum 时间复杂度findMedian 时间复杂度空间复杂度优点缺点双堆法O(log n)O(1)O(n)高效常用需维护两个堆有序列表O(n)O(1)O(n)简单插入慢平衡树O(log n)O(log n)O(n)通用实现复杂插入排序O(n)O(1)O(n)简单插入慢懒删除双堆O(log n)O(1)O(n)支持删除实现复杂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){intnnums.length;double[]resultnewdouble[n-k1];MedianFinderWithDeletemfnewMedianFinderWithDelete();for(inti0;in;i){mf.addNum(nums[i]);if(ik){mf.removeNum(nums[i-k]);}if(ik-1){result[i-k1]mf.findMedian();}}returnresult;}}注此处使用前面实现的MedianFinderWithDelete类5.2 变体二数据流中的第K大元素题目描述设计一个类从数据流中接收元素并能随时返回当前第 k 大的元素。Java代码实现importjava.util.PriorityQueue;classKthLargest{privatePriorityQueueIntegerminHeap;privateintk;publicKthLargest(intk,int[]nums){this.kk;minHeapnewPriorityQueue(k);for(intnum:nums){add(num);}}publicintadd(intval){if(minHeap.size()k){minHeap.offer(val);}elseif(valminHeap.peek()){minHeap.poll();minHeap.offer(val);}returnminHeap.peek();}}5.3 变体三数据流中的众数题目描述实时返回数据流中出现次数最多的元素若有多个返回任意一个。Java代码实现importjava.util.*;classMajorityFinder{privateMapInteger,Integerfreq;privatePriorityQueueMap.EntryInteger,IntegermaxHeap;publicMajorityFinder(){freqnewHashMap();maxHeapnewPriorityQueue((a,b)-b.getValue()-a.getValue());}publicvoidadd(intnum){freq.put(num,freq.getOrDefault(num,0)1);// 更新堆懒删除每次查询时重建或使用更高效方法// 为简单每次查询时重建堆}publicintgetMajority(){// 重建堆实际效率低仅示意maxHeap.clear();for(Map.EntryInteger,Integere: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 常见面试问题QAQ1为什么需要两个堆A1因为中位数需要将数据分成左右两部分两个堆分别维护这两部分且能快速获取左右的最大值和最小值。Q2如何保证两个堆的大小平衡A2通过每次插入后调整确保size_maxHeap size_minHeap且差值 ≤ 1。常见的调整方式先插入最大堆再移一个到最小堆再根据大小调整。Q3如果有大量重复元素堆法有效吗A3有效因为堆只比较元素值重复元素会被正常处理。Q4能否用一个堆实现A4不能因为一个堆无法同时获取最大值和最小值也无法确定中位数位置。Q5数据流的中位数可以扩展到多个数据流吗A5可以但需要更复杂的数据结构如对顶堆的扩展或使用平衡树。
相关文章
低代码运行时“黑盒”报错不显示堆栈？揭秘CPython字节码层调试协议v3.11+的7个未公开Hook点
第一章：低代码运行时“黑盒”报错的典型现象与根因定位困境在低代码平台的实际交付过程中，开发者常遭遇运行时错误无法准确定位的困境：界面无明确提示、控制台仅输出模糊异常（如 Runtime Error: Unknown node type）&am…
JS 异步：Event-Loop+async/await
前言在前端开发中，是不是经常被JS的异步代码绕晕？明明写的代码顺序一样，运行结果却大相径庭？其实核心原因就在于——JS是单线程语言，而异步操作全靠「Event-Loop（事件循环）」来调度。今天就结合…
从 i.MX6ULL 谈 ARM Cortex-A7 与 ARMv7-A 架构核心知识点
在嵌入式开发领域，NXP 的 i.MX6ULL 是一款应用极为广泛的 32 位工业级处理器，凭借低功耗、高性价比的特性成为物联网、工业控制、智能终端等场景的优选方案。而深入理解 i.MX6ULL 的核心架构，绕不开其搭载的 ARM Cortex-A7 内核与 ARMv7-A 指…
变体无人机间歇滑翔控制：利用上升气流提升续航的工程实践
1. 项目概述与核心价值 在无人机领域，续航能力始终是制约其任务效能的关键瓶颈。无论是执行长距离侦察、广域监测还是定点物流，有限的能源都像一道无形的枷锁。传统的解决方案，如增大电池容量或优化气动外形，往往伴随着重量增加或…
理解AI的六个思维隐喻：从贴标机到智能尺度的认知工具
1. 理解人工智能的六个思维隐喻在技术浪潮席卷的今天，人工智能（AI）已经从一个科幻概念，变成了我们日常工作与生活中无法回避的现实。无论是社交媒体上的内容推荐，还是手机里的语音助手，亦或是工厂里的自动化…
告别Windows Defender误报困扰：开源神器Defender Control实战指南
告别Windows Defender误报困扰：开源神器Defender Control实战指南 【免费下载链接】defender-control An open-source windows defender manager. Now you can disable windows defender permanently. 项目地址: https://gitcode.com/gh_mirrors/de/defender-con…
5分钟实现专业论文排版：Microsoft Word APA第7版格式终极方案
5分钟实现专业论文排版：Microsoft Word APA第7版格式终极方案 【免费下载链接】APA-7th-Edition Microsoft Word XSD for generating APA 7th edition references 项目地址: https://gitcode.com/gh_mirrors/ap/APA-7th-Edition 还在为学术论文的参考文献格式…
ImageGlass终极指南：90+格式支持的高效开源图片浏览器深度解析
ImageGlass终极指南：90格式支持的高效开源图片浏览器深度解析 【免费下载链接】ImageGlass 🏞 A fast, open-source, modern image viewer for 90 formats – including WEBP, GIF, SVG, AVIF, JXL, HEIC and more – built for smooth browsing across …
基于2SC3858与TTA1943的互补对称功放电路设计与制作指南
1. 项目概述与核心价值如果你对电子制作感兴趣，尤其是想亲手打造一个声音洪亮、成本低廉的音频放大器，那么今天分享的这个基于2SC3858和TTA1943晶体管的电路方案，绝对值得你花时间研究。音频放大器，简单来说就是一个“声音助推器”…
Zotero Duplicates Merger：5步彻底清理文献库重复条目
Zotero Duplicates Merger：5步彻底清理文献库重复条目 【免费下载链接】ZoteroDuplicatesMerger A zotero plugin to automatically merge duplicate items 项目地址: https://gitcode.com/gh_mirrors/zo/ZoteroDuplicatesMerger 还在为文献库中堆积如山的重…
利用随机有限集理论对蜂群的ILQR和MPC控制研究附Matlab代码
✅作者简介：热爱科研的Matlab仿真开发者，擅长数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。🍎 往期回顾关注个人主页：Matlab科研工作室🍊个人信条：格物致知,完整Matlab代码及仿真咨询…
为什么你的Gemini邮件CTE低于行业均值2.8倍？：从Prompt架构到发送时序的深度归因
更多请点击： https://intelliparadigm.com 第一章：为什么你的Gemini邮件CTE低于行业均值2.8倍？：从Prompt架构到发送时序的深度归因 Gemini邮件的客户转化效率（CTE）显著偏低，根本原因常被误判为…
Win10/Win11下Realtek 8188GU网卡驱动感叹号？别急着扔，试试这个手动安装的野路子
Realtek 8188GU网卡驱动故障深度修复指南：从原理到实战当设备管理器里那个顽固的黄色感叹号挥之不去，而你已经尝试了所有"标准操作"——Windows自动更新、第三方驱动工具、甚至重启大法——却依然无济于事时，是时候换个思路了。这篇…
AnolisOS 8.8安装源配置踩坑实录：从‘设置基础软件仓库时出错’到成功联网的保姆级指南
AnolisOS 8.8安装源配置实战指南：从诊断到解决方案的全流程解析当你在安装AnolisOS 8.8时遇到"设置基础软件仓库时出错"的提示，这通常意味着系统无法访问或识别安装源。这个问题看似简单，但背后可能涉及网络配置、镜像选择、启动参…
基于树莓派Pico的反应速度测试游戏：从GPIO编程到状态机实战
1. 项目概述与核心思路最近在整理工作室的电子元件，翻出来几个闲置的街机按钮和一块树莓派Pico，灵机一动，决定做个简单又有趣的反应速度测试游戏。这个项目非常适合想入门嵌入式开发的朋友，它不涉及复杂的传感器和通信协议&#x…
Zotero Duplicates Merger：5步彻底清理文献库重复条目
Zotero Duplicates Merger：5步彻底清理文献库重复条目 【免费下载链接】ZoteroDuplicatesMerger A zotero plugin to automatically merge duplicate items 项目地址: https://gitcode.com/gh_mirrors/zo/ZoteroDuplicatesMerger 还在为文献库中堆积如山的重…
利用随机有限集理论对蜂群的ILQR和MPC控制研究附Matlab代码
✅作者简介：热爱科研的Matlab仿真开发者，擅长数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。🍎 往期回顾关注个人主页：Matlab科研工作室🍊个人信条：格物致知,完整Matlab代码及仿真咨询…
为什么你的Gemini邮件CTE低于行业均值2.8倍？：从Prompt架构到发送时序的深度归因
更多请点击： https://intelliparadigm.com 第一章：为什么你的Gemini邮件CTE低于行业均值2.8倍？：从Prompt架构到发送时序的深度归因 Gemini邮件的客户转化效率（CTE）显著偏低，根本原因常被误判为…