一、题目内容

二、题解

解法1：

思路

双堆，一个大堆一个小堆
大堆存储较小的数据，堆顶为堆的最大值
小堆存储较大的数据，堆顶为堆的最小值

使用优先队列 PriorityQueue

代码

public class MedianFinder {
    Queue<Integer> min_heap, max_heap;
    /**
     * min_heap    max_heap
     * max->min    min->max
     * initialize your data structure here.
     */
    public MedianFinder() {
        min_heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //升序
                return o1 - o2;
            }
        }); // 小顶堆，保存较大的一半
        max_heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //降序
                return o2 - o1;
            }
        }); // 大顶堆，保存较小的一半
    }
    /**
     * 如果两个数组相等：大顶堆+1
     * 不相等：小顶堆+1
     *
     * @param num
     */
    public void addNum(int num) {
        if (min_heap.size() != max_heap.size()) {
            min_heap.add(num);
            max_heap.add(min_heap.poll());
        } else {
            max_heap.add(num);
            min_heap.add(max_heap.poll());
        }
    }
    public double findMedian() {
        return min_heap.size() != max_heap.size() ? min_heap.peek() : (min_heap.peek() + max_heap.peek()) / 2d;
    }
}

解法2：

思路

类似插入排序，通过二分查找，找到小的大于num的index；如果均小于则追加末尾

代码

class MedianFinder {
    private ArrayList<Integer> list;
    /** initialize your data structure here. */
    public MedianFinder() {
        list = new ArrayList<Integer>();
    }
    /**
     * 插入
     *
     * @param num
     */
    public void addNum(int num) {
        if (list.isEmpty()) {
            list.add(num);
            return;
        }
        int maxIndex = list.size() - 1;
        int pos = findPos(num);
        //如果返回的可插入位置大于最大index，则直接追加，否则插入pos位置，pos后数据顺序移动一位
        if (pos > maxIndex) {
            list.add(num);
        } else {
            list.add(findPos(num), num);
        }
    }
    //找到第一个大于nums的index；如果均小于num，则返回 maxIndex+1
    public int findPos(int num) {
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (list.get(mid) > num) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (list.get(right) > num) {
            return right;
        } else {
            return right + 1;
        }
    }
    // 奇数  len/2
    // 偶数  (len/2-1   +  len/2 ) /2d
    public double findMedian() {
        int len = list.size();
        if (len % 2 == 0) {
            return (list.get(len / 2 - 1) + list.get(len / 2)) / 2d;
        } else {
            return list.get(len / 2);
        }
    }
}