剑指Offer(41) 数据流中的中位数

发表于 | 分类于 | 阅读次数:
字数统计: 858 | 阅读时长 ≈ 3

数据流中的中位数

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

思路

所谓数据流，就是不会一次性读入所有数据，只能一个一个读取，每一步都要求能计算中位数。

　　将读入的数据分为两部分，一部分数字小，另一部分大。小的一部分采用大顶堆存放，大的一部分采用小顶堆存放。当总个数为偶数时，使两个堆的数目相同，则中位数=大顶堆的最大数字与小顶堆的最小数字的平均值；而总个数为奇数时，使小顶堆的个数比大顶堆多一，则中位数=小顶堆的最小数字。

因此，插入的步骤如下：

　　1. 若已读取的个数为偶数（包括0）时，两个堆的数目已经相同，将新读取的数插入到小顶堆中，从而实现小顶堆的个数多一。但是，如果新读取的数字比大顶堆中最大的数字还小，就不能直接插入到小顶堆中了 ，此时必须将新数字插入到大顶堆中，而将大顶堆中的最大数字插入到小顶堆中，从而实现小顶堆的个数多一。

　　2. 若已读取的个数为奇数时，小顶堆的个数多一，所以要将新读取数字插入到大顶堆中，此时方法与上面类似。

测试用例

  1. 功能测试（读入奇/偶数个数字）

  2. 边界值测试（读入0个、1个、2个数字）

jav代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * @description:
 * @author: rhsphere
 * @since: 2019-07-29 21:52 by jdk 1.8
 */
public class StreamMedian {
	PriorityQueue<Integer> minHeap = new PriorityQueue<>();  //小顶堆，默认容量11
	PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, new Comparator<Integer>{
		public int compare(Integer i1, Integer i2) {
			return i2 - i1; 
		}
	});

	public void insert(Integer num) {
		if (((minHeap.size() + maxHeap.size()) & 1) == 0) {
			//偶数个时，下个数字加入小顶堆
			if (!maxHeap.isEmpty() && maxHeap.peek() > num) {
				maxHeap.offer(num);
				num = maxHeap.poll();
			}
			minHeap.offer(num);
		} else {
			//奇数个时，下个数字放入大顶堆
			if (!minHeap.isEmpty() && minHeap.peek() < num) {
				minHeap.offer(num);
				num = minHeap.poll();
			}
			maxHeap.offer(num);
		}
	}

	public Double getMedian() {
		if ((maxHeap.size() + minHeap.size()) == 0)
			throw new RuntimeException();
		double median;
		if (((minHeap.size() + maxHeap.size()) & 1) == 0) {
			median = (maxHeap.peek() + minHeap.peek()) / 2.0;
		} else {
			median = minHeap.peek();
		}
		return median;
	}
}

总结

  1. 最大堆 最小堆其实就是优先队列，这里可以用PriorityQueue实现，PriorityQueue默认是一个小顶堆，通过传入自定义的Comparator函数，可以实现大顶堆：
1
2
3
4
5
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>(){
	public int compare(Integer i1, Integer i2) {
		retrurn i2 - i1;  //降序排列
	}
});

PriorityQueue的常用方法有： poll()、 offer(Object)、 size()、 peek()等。

  1. 平均值定义为double，且 (a+b）/2.0 。
  2. 往最大堆中插入数据时间复杂度是O(logn)，获取最大数的时间复杂度是O(1)。
  3. 这道题关键在于分成两个平均分配的部分，奇偶时分别插入到最大最小堆中，利用最大最小堆性质的插入方法要掌握。
0%