首页 技术 正文
技术 2022年11月23日
0 收藏 999 点赞 2,138 浏览 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.5
addNum(3)
findMedian() -> 2

此题要找出数据流的中位数,数据流由无序整数组成,并且数据流是在变化的。中位数的定义是,如果数字个数为偶数,中位数就是中间两个数的平均数,如果是奇数,中位数是中间那个数字。

解法1: 最简单的想法是,每进来一个数字后,插入排序整个数组,保持数组是有序的,然后分奇偶的情况找到中位数。此方法不高效。

解法2: 堆Heap,将进来的数据流分成大小两个堆,分别保存堆的前半部分和后半部分,大堆是最小数字在堆顶,小堆是最大数在堆顶。取中间值时,根据两个堆的数字个数,如果个数相同,就各取堆顶数字取平均数就是中间数,如果有一个堆数字多1,中间数就是这个堆顶数字。

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 题目汇总

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141790.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,071
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,505
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,316
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,311
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,911
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,099
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站