295-计算数据流的中位数

Description:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

---

Examples:

[2,3,4] , the median is 3 [2,3], the median is (2 + 3) / 2 = 2.5

---

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.double findMedian() - Return the median of all elements so far.

---

For example:

addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2

---

问题描述:

设计一个数据结构，支持以下两个操作:

addNum(int num)-从数据流向数据结构中添加一个整数findMedian()-返回至今所有元素的中位数

---

问题分析:

这道题的前置问题是: https://leetcode.com/problems/sliding-window-median/description/ 思路: 维护两个优先级队列: 1. maxQueue,队列逆序 2. minQueue

对于这两个优先级队列，需要维护两个特征 1. maxQueue保存小于等于中位数的元素，minQueue保存大于中位数的元素 2. maxQueue的元素个数严格控制在minQueue <= maxQueue <= minQueue + 1

如何求中位数? 分两种情况： 1. size(maxQueue) == size(minQueue),返回maxQueue的第一个元素和minQueue的第一个元素的平均数 2. size(maxQueue) = size(minQueue) + 1,返回maxQueue的第一个元素

---

解法:

class MedianFinder { PriorityQueue<Integer> minQueue; PriorityQueue<Integer> maxQueue; int maxsize = 0; int minsize = 0; /** initialize your data structure here. */ public MedianFinder() { minQueue = new PriorityQueue(); maxQueue = new PriorityQueue(Collections.reverseOrder()); } public void addNum(int num) { if(num <= findMedian()){ maxQueue.offer(num); maxsize++; }else{ minQueue.offer(num); minsize++; } if(maxsize < minsize){ maxQueue.offer(minQueue.poll()); maxsize++; minsize--; }else if(maxsize > minsize + 1){ minQueue.offer(maxQueue.poll()); maxsize--; minsize++; } } public double findMedian() { if(maxsize == 0 && minsize == 0) return 0; if(maxsize == minsize){ return (maxQueue.peek() + minQueue.peek()) / 2.0; }else{ return maxQueue.peek(); } } }