【剑指offer】面试题41：数据流中的中位数

系统管理员 2022-04-22 15:04 145阅读 0赞

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

由于数据是从一个数据流中读出来的，因而数据的数目随着时间的变化而增加的。如果用一个数据容器来保存从流中读出来的数据，则当有新的数据从流中读出来时，这些数据就插入数据容器。这个数据容器可以用很多的数据结构实现，比如：数组、链表、二叉搜索树、AVL树、最大堆和最小堆等等。

如果能够保证数据容器左边的数据都小于右边数据，那么即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个容器中找出最大数呢？用最大堆实现这个数据容器，因为位于堆顶的就是最大数据。同样，也可以快速从最小堆中找出最小数。

因此，可以用如下思路来解决这个问题：**用一个最大堆实现左边的数据容器，用一个最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是 O(logn)。由于只需要O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间复杂度是O(1)。**

下面来考虑用最大堆和最小堆实现的一些细节：

1、首先要保证数据平均分配到两个堆中，因此两个堆中数据的数目之差不能超过1。为了实现平均分配，可以在数据的总数目是偶数时把新数据插入最小堆，否则插入最大堆。

2、还要保证最大堆中的所有数据都要小于最小堆中的数据。当数据的总数目是偶数时，按照前面的分配规则会把新的数据插入最小堆。如果此时这个新的数据比最大堆中的一些数据要小，那该怎么办呢？可以先把这个新的数据插入最大堆，接着把最大堆中最大的数字拿出来插入最小堆。由于最终插入最小堆的数字是原来堆中最大的数字，这样就保证了最小堆中所有数字都大于最大堆中的数字。

3、当需要把一个数据插入最大堆，但这个数据大于最小堆里的一些数据时，这个情形和前面类似。

代码实现如下：

package com.zju.offer.number;
    
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    /**
     * 如何得到一个数据流中的中位数？
     */
    public class FindMedianNum {
    
    	// count为奇数时进入小顶堆，为偶数时进入大顶堆
    	private int count = 0;
    	private PriorityQueue<Integer> minHeap = new PriorityQueue();
    	private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>(){
    
    		@Override
    		public int compare(Integer o1, Integer o2) {
    			return o2 - o1;
    		}
    	});
    	
            /**
                     * 读取数据流中的元素 
                     */
    	public void insert(Integer num){
    		if(count %2 == 0){
    			// 当数据总数为偶数时，新加入的元素，应当进入小顶堆
    			// 需要注意的是：并不是直接进入小顶堆，而是经大顶堆筛选后取大顶堆中最大元素进入小顶堆
    			// 1、新加入的元素进入大顶堆，由大顶堆筛选出堆中最大元素
    			maxHeap.offer(num);
    			int filteredMaxNum = maxHeap.poll();
    			// 2、筛选后，即大顶堆中的最大元素进入小顶堆
    			minHeap.offer(filteredMaxNum);
    		}else{
    			// 当数据总数为奇数时，新加入的元素，应当进入大顶堆
    			// 需要注意的是：不是直接进入大顶堆，而是经小顶堆筛选后取出小顶堆中最小元素进入大顶堆
    			// 1、新加入的元素先进入小顶堆，由小顶堆筛选出堆中最小元素
    			minHeap.offer(num);
    			int filteredMinNum = minHeap.poll();
    			// 2、筛选后的，即小顶堆中的最小元素进入大顶堆
    			maxHeap.offer(filteredMinNum);
    		}
    		count++;
    	}
    	
            /**
                     * 获取当前读取数据的中位数 
                     */
    	public Double getMedian(){
    		if(count %2 == 0){
    			return new Double((minHeap.peek() + maxHeap.peek())) / 2;
    		}else{
    			return new Double(minHeap.peek());
    		}
    	}
    }