当前位置:网站首页>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。
边栏推荐
猜你喜欢
From September 1st, my country has granted zero-tariff treatment to 98% of tax items from 16 countries including Togo
小朋友学C语言(1):Hello World
基于支持向量机的网络⼊侵检测系统的全面调查和分类
HCIP第十五天
2021年数据泄露成本报告解读
Transformer怎么入门?如何学习Transformer?
XSS测试
IO线程进程->线程同步互斥机制->day6
深度学习和机器学习有什么区别?
Linux操作Jmeter(附带:关于连接上redis无法进行写入操作的问题),JMeter配置多用户进行压力测试
随机推荐
LitJson报错记录
Soft exam system analysts note experience sharing: theory of protracted war
字节跳动软件测试岗,前两面过了,第三面HR天坑,结局透心凉...
Use setTimeout to realize setInterval
CAS:1260586-88-6_Biotin-C5-Azide_Biotin-C5-Azide
解决npm -v查看npm版本出现npm WARN config global `--global`, `--local` are deprecated. Use `--location报错
D - Project Planning--二分
Cross-end development technical reserve record
软考系统分析师备考经验分享:论持久战
CC2530_ZigBee+华为云IOT:设计一套属于自己的冷链采集系统
从0到1看支付
B. Kalindrome Array
CAS: 773888-45-2_BIOTIN ALKYNE_生物素-炔基
软件测试人员必备的60个测试工具清单,建议收藏一波~
剑指 Offer 16. 数值的整数次方
2021年数据泄露成本报告解读
gtk实现图片旋转
nxp官方uboot移植到野火开发板PRO(无任何代码逻辑的修改)
IDaaS 是什么?一文说清它的价值
[3D检测系列-PV-RCNN] PV-RCNN论文详解、PV-RCNN代码复现、包含官网PV-RCNN预训练权重及报错问题