76-数据流中的中位数

题⽬描述

如何得到⼀个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使⽤ Insert() ⽅法读取数据流，使⽤ GetMedian() ⽅法获取当前读取数据的中位数。

思路及解答

⽤⼀个数字来不断统计数据流中的个数，并且创建⼀个最⼤堆，⼀个最⼩堆

• 如果插⼊的数字的个数是奇数的时候，让最⼩堆⾥⾯的元素个数⽐最⼤堆的个数多 1 ，这样⼀来中位数就是⼩顶堆的堆顶
• 如果插⼊的数字的个数是偶数的时候，两个堆的元素保持⼀样多，中位数就是两个堆的堆顶的元素相加除以2 。

public class Solution {
	private int count = 0;
	private PriorityQueue<Integer> min = new PriorityQueue<Integer>();
	private PriorityQueue<Integer> max = new PriorityQueue<Integer>(new
	
	Comparator<Integer>() {
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}
	});
	
	public void Insert(Integer num) {
		count++;
		if (count % 2 == 1) {
			// 奇数的时候，需要最⼩堆的元素⽐最⼤堆的元素多⼀个。
			// 先放到最⼤堆⾥⾯，然后弹出最⼤的
			max.offer(num);
			// 把最⼤的放进最⼩堆
			min.offer(max.poll());
		} else {
			// 放进最⼩堆
			min.offer(num);
			// 把最⼩的放进最⼤堆
			max.offer(min.poll());
		}
	}
		
	public Double GetMedian() {
		if (count % 2 == 0) {
			return (min.peek() + max.peek()) / 2.0;
		} else {
			return (double) min.peek();
		}
	}
}

• 空间复杂度为 O(n)
• 取出中位数的时间复杂度为 O(1) ，
• 添加数据的时间复杂度为O(nlogn)：这是因为每次插⼊的时候，使⽤了堆处理数据