# [LeetCode] 295. Find Median from Data Stream 找出数据流的中位数

2022年11月23日
0 收藏 999 点赞 2,170 浏览 2452 个字

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.

For example,

`[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.

Example:

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

Java:

`class MedianFinder {    PriorityQueue<Integer> maxHeap;//lower half    PriorityQueue<Integer> minHeap;//higher half    public MedianFinder(){        maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());        minHeap = new PriorityQueue<Integer>();    }    // Adds a number into the data structure.    public void addNum(int num) {        maxHeap.offer(num);        minHeap.offer(maxHeap.poll());        if(maxHeap.size() < minHeap.size()){            maxHeap.offer(minHeap.poll());        }    }    // Returns the median of current data stream    public double findMedian() {        if(maxHeap.size()==minHeap.size()){            return (double)(maxHeap.peek()+(minHeap.peek()))/2;        }else{            return maxHeap.peek();        }    }}　`

Python:

`from heapq import heappush, heappopclass MedianFinder:    def __init__(self):        """        Initialize your data structure here.        """        self.__max_heap = []        self.__min_heap = []    def addNum(self, num):        """        Adds a num into the data structure.        :type num: int        :rtype: void        """        # Balance smaller half and larger half.        if not self.__max_heap or num > -self.__max_heap[0]:            heappush(self.__min_heap, num)            if len(self.__min_heap) > len(self.__max_heap) + 1:                heappush(self.__max_heap, -heappop(self.__min_heap))        else:            heappush(self.__max_heap, -num)            if len(self.__max_heap) > len(self.__min_heap):                heappush(self.__min_heap, -heappop(self.__max_heap))    def findMedian(self):        """        Returns the median of current data stream        :rtype: float        """        return (-self.__max_heap[0] + self.__min_heap[0]) / 2.0 \               if len(self.__min_heap) == len(self.__max_heap) \               else self.__min_heap[0]`

C++:

`class MedianFinder {public:    // Adds a number into the data structure.    void addNum(int num) {        small.push(num);        large.push(-small.top());        small.pop();        if (small.size() < large.size()) {            small.push(-large.top());            large.pop();        }    }    // Returns the median of current data stream    double findMedian() {        return small.size() > large.size() ? small.top() : 0.5 *(small.top() - large.top());    }private:    priority_queue<long> small, large;};`

# All LeetCode Questions List 题目汇总

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用

400-888-8888

ceotheme@ceo.com