随时找到数据流的中位

本文主要是介绍随时找到数据流的中位，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】 有一个源源不断地吐出整数的数据流，假设你有足够的空间来 保存吐出的数。请设计一个名叫MedianHolder的结构， MedianHolder可以随时取得之前吐出所有数的中位数。

【要求】 1．如果MedianHolder已经保存了吐出的N个数，那么任意时刻 将一个新数加入到MedianHolder的过程，其时间复杂度是 O(logN)。 2．取得已经吐出的N个数整体的中位数的过程，时间复杂度为 O(1)

寻找中位数是十分简单的,一串数据，排好序后，length为偶数就是中间的两个数的平均数。。。奇数为中间的数，，，小学知识

但是每次新进来一个数都要经历排序，每次排序的时间复杂度是远远大于O(1)的

方案

使用java提供的内置堆结构

堆结构简单来说就是，分为大根堆、小根堆

大根堆无论如何增删数据，第一个永远是最大的数据

小根堆同理

想详细理解的的请去熟悉下堆排序：堆排序

规则：

我们用一个大根堆Max、和一个小根堆Min去各自盛放这组数据的前一半、和后一半

那么前一半最大的数永远在第一个、后一半最小的数永远在第一个

执行规则：

进来一个数，当Max为空时：加入Max堆else

这个数小于等于Max头部元素时，加入Max堆，else加入Min堆

--每次进数后，判断两个堆的大小是否差值大于1，如果大于1让比较多的那个堆从堆顶弹出一个给另一堆

一组示范

假设一组数据

5、3、1、0、2、4  --每个以次加入MedianHolder并获取中位数

当max为空时直接入Max

3、1、0、2、4

Max:5

Min:

此时只有一个数，他的中位数就是5

当max不为空时、判断下一个进来的数是否小于等于Max头部元素，是就加入Max

1、0、2、4

MaxPlie:5、3

MinPlie:

由于这样会导致两个堆中的数据量不平衡，规定，某个堆长度大于另一个堆1的时候无条件将头部元素给另一个堆

将5弹出给Min

MaxPlie:3

MinPlie:5

此时已经进入的数据中位数就是（5+3）/2=4

进来一个数1小于等于Max堆顶加入Max

0、2、4

Max:3、1

Min:5

中位数3

进来一个数0小于等于Max堆顶加入Max

2、4

Max:3、1、0

Min:5

需要铺平（差值过大，弹出一个给小的堆）

Max:1、0

Min:3、5

中位数 (1+3)/2=2

进来一个数2大于于Max堆顶加入Min堆

4

Max:1、0

Min:2、3、5

中位数2

进来一个数4大于Max堆顶加入Min堆

Max:1、0

Min:2、3、5、4

差值过大、需要铺平

Max:2、1、0

Min:3、5、4

中位数(2+3)/2=2.5

附加学习理解功能的代码

package basic_class_04;
import java.util.*;
public class Main {//快速中位数类public static class MedianHolder{//堆结构默认的是小根堆，，，这里插入一个比较器使堆变成大根堆private PriorityQueue<Integer> MaxHeap = new PriorityQueue<Integer>(11,new MaxSort());private PriorityQueue<Integer> MinHeap = new PriorityQueue<Integer>();public void addNumber(int num){if(MaxHeap.isEmpty()){MaxHeap.add(num);return;}if(num<=MaxHeap.peek()){MaxHeap.add(num);}else{MinHeap.add(num);}modifyTwoHeapsSize();// 每次添加后将两个堆铺平}public void modifyTwoHeapsSize(){if(MaxHeap.size()-MinHeap.size()==2){MinHeap.add(MaxHeap.poll());}if(MinHeap.size()-MaxHeap.size()==2){MaxHeap.add(MinHeap.poll());}}public Integer getMedian(){//取中位数，需要判断总数据量是奇数还是偶数int maxHeapSize = this.MaxHeap.size();int minHeapSize = this.MinHeap.size();if (maxHeapSize + minHeapSize == 0) {return null;}Integer maxHeapHead = this.MaxHeap.peek();Integer minHeapHead = this.MinHeap.peek();if(maxHeapSize==minHeapSize){return (maxHeapHead+minHeapHead)/2;}return maxHeapSize>minHeapSize?maxHeapHead:minHeapHead;}private static class MaxSort implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {// TODO Auto-generated method stubreturn o2-o1;}}}public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = {5,3,1,0,2,4};MedianHolder Medians = new MedianHolder();int[] newarr;int median;for(int i=0;i<arr.length;i++){newarr = Arrays.copyOfRange(arr,0,i);System.out.println(Arrays.toString(newarr));Medians.addNumber(arr[i]);System.out.println("+"+arr[i]);newarr = Arrays.copyOfRange(arr,0,i+1);System.out.println(Arrays.toString(newarr));median = Medians.getMedian();System.out.println("中位数"+median);System.out.println();}}}

不懂比较器?

比较器

这篇关于随时找到数据流的中位的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---