当前位置:网站首页>480. Sliding Window Median
480. Sliding Window Median
2022-08-03 21:45:00 【51CTO】
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
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Therefore, return the median sliding window as [1,-1,-1,3,5,6].
Note:
You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.
思路:
这题和那道Find Median from Data Stream比起来多加了个sliding window。那道题巧妙的用了两个heap来找到mean,还有道题是Slide Window Maximum,同样是slide window的题。还是用两个heap来做,remove这个操作复杂度用了logk。minHeap和maxHeap,maxHeap在保存较小的一半元素,minHeap保存较大的一半元素,0 <= minHeap.size() - maxHeap.size() <= 1,注意maxheap写的时候不能用a - b,因为可能overflow。
边栏推荐
- XSS testing
- 2022-8-3 第七组 潘堂智 锁、多线程
- 电商数仓ODS层-----日志数据装载
- CAS:908007-17-0_Biotin-azide_Biotin azide
- 全球观之地理部分
- 什么密码,永远无法被黑客攻破?
- Markdown syntax
- Data_web(九)mongodb增量同步到mongodb
- From September 1st, my country has granted zero-tariff treatment to 98% of tax items from 16 countries including Togo
- StoneDB 开源社区月刊 | 202207期
猜你喜欢
随机推荐
From September 1st, my country has granted zero-tariff treatment to 98% of tax items from 16 countries including Togo
安全基础8 ---XSS
Nacos配置文件管理、微服务获取Nacos配置文件
反射机制
字节跳动软件测试岗,前两面过了,第三面HR天坑,结局透心凉...
idea2021.1.3配置Gradle步骤
小朋友学C语言(1):Hello World
CAS: 1192802-98-4 _uv cracking of biotin - PEG2 - azide
HCIP第十五天
什么密码,永远无法被黑客攻破?
《强化学习周刊》第56期:GraphIRL、REDEEMER & 眼科强化学习的潜在研究
Interesting opencv - record image binarization and similarity
【kali-漏洞扫描】(2.1)Nessus下载安装(上)
DO280管理和监控OpenShift平台--资源限制
线程池的高级应用技巧核心解读
CC2530_ZigBee+华为云IOT:设计一套属于自己的冷链采集系统
CAS:1797415-74-7_TAMRA-Azide-PEG-Biotin
主板设计中:网络变压器与RJ45网口之间应该保持什么样的距离?
IDaaS 是什么?一文说清它的价值
What is the role and difference between buildscript and allprojects?