剑指Offer_63

发表于 | 分类于

题目

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

解题思路

a. 最小堆放大数，最大堆放大数，那么两个堆的堆顶就是逼近中位数的数

b. count计数，当两堆数目一样时候，优先放在最小堆

c. 插入最大、最小堆的时候，先到对方的堆中换取合适的值

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
44
45
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
	private int count = 0;
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
        @Override
        public int compare(Integer o1, Integer o2){
            return o2 - o1;
        }
    });
    
    public void Insert(Integer num) {
    
    	//往最小堆插入数据，num进入最大堆，
    	//取出最大堆现在最大的数据
    	//插入最小堆
    	if(count % 2 == 0){
            maxHeap.offer(num);
            int maxHeapMax = maxHeap.poll();
            minHeap.offer(maxHeapMax);
        }
        //往最大堆插入数据，num进入最小堆
        //取出最小堆现在最大的数据
        //插入最小堆
        else{
            minHeap.offer(num);
            int minHeapMin = minHeap.poll();
            maxHeap.offer(minHeapMin);
        }
        ++count;
    }
    public Double GetMedian() {
        if(count % 2 == 0){
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        }
        else{
            return (double)minHeap.peek();
        }
    }
}