数据流中的中位数解法

背景介绍

越来越多的程序员关注数据结构和算法的知识，会在leetcode和牛客等各种网站刷题，但是遇到一些中等难度或者困难难度的题就束手无策，而我通过刷题来写一些关于中等或者困难的题目的题解，达到一个自己越来越熟悉，而且还可以帮助别人理解的程度。接下来我会用两种策略来解决这道题——数据流中的中位数。

数据流中的中位数解法

Problem

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

Solution（两种解决策略）

解决策略1

建立一个大根堆和一个小根堆，用一个临时变量（count）来统计数据流的个数
当插入的数字个数为奇数时，使小根堆的个数比大根堆多1；当插入的数字个数为偶数时，使大根堆和小根堆的个数一样多
当总的个数为奇数时，中位数就是小根堆的堆顶；当总的个数为偶数时，中位数就是两个堆顶的值相加除以2

Code1

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author god-jiang
 * @date 2020/1/3
 */
public class MedianFinder {
    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;
        }
    });
    //统计数据流的个数
    private int count = 0;
    //确保小根堆里面的数 > 大根堆里面的数
    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();
    }
}

Test1

解决策略2

建立一个大根堆和一个小根堆，必须确保满足两点：
- 小根堆里面的数 > 大根堆里面的数
- 大根堆和小根堆的个数差值必须 <= 1
当总的个数为偶数时：
- 中位数就是（大根堆堆顶+小根堆堆顶）/ 2.0
当总的个数为奇数时：
- 大根堆的个数 > 小根堆的个数，则中位数就是大根堆的堆顶
- 大根堆的个数 < 小根堆的个数，则中位数就是小根堆的堆顶

Code2

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author god-jiang
 * @date 2020/1/3
 */
public class MedianFinder {
    PriorityQueue<Integer> min = null;
    PriorityQueue<Integer> max = null;
    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        //默认从小到大排序
        min = new PriorityQueue<>();
        //修改比较器，让他从大到小排序
        max = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
    }

    public void addNum(int num) {
        //进来一个树先判断是不是小于大根堆堆顶，是就放大根堆，不是放小根堆
        if (max.size() == 0 || max.peek() > num) {
            max.add(num);
        } else {
            min.add(num);
        }
        //保证两个堆的个数相差不大于1
        if (min.size() - max.size() > 1) {
            max.add(min.poll());
        }
        if (max.size() - min.size() > 1) {
            min.add(max.poll());
        }
    }

    public double findMedian() {
        int count = max.size() + min.size();
        //判断总的个数是否为偶数
        if ((count & 1) == 0) {
            return (max.peek() + min.peek()) / 2.0;
        }
        //总的个数是奇数的情况
        if (max.size() > min.size()) {
            return max.peek() / 1.0;
        }
        return min.peek() / 1.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */