leetcode如何找出滑动窗口中位数
发表于:2025-01-26 作者:千家信息网编辑
千家信息网最后更新 2025年01月26日,小编给大家分享一下leetcode如何找出滑动窗口中位数,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!中位数是有序序列最中间的那个数。如果序列的大小是偶数,则没有最中间的数;此时中位
千家信息网最后更新 2025年01月26日leetcode如何找出滑动窗口中位数
小编给大家分享一下leetcode如何找出滑动窗口中位数,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!
中位数是有序序列最中间的那个数。如果序列的大小是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。
例如:
[2,3,4]
,中位数是 3
[2,3]
,中位数是 (2 + 3) / 2 = 2.5
给出一个数组 nums,有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数,每次窗口移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数,并输出由它们组成的数组。
例如:
给出 nums = [1,3,-1,-3,5,3,6,7]
,以及 k = 3。
窗口位置 中位数
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
因此,返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]
。
提示:
假设k
是合法的,即:k
始终小于输入的非空数组的元素个数.
解题思路:
1,注意中位数是窗口内数据排序后的中位数
2,对于窗口内部可以采用插入排序的思想进行排序
3,初始时,采用插入排序,将前k个值,插入窗口
4,找到左指针对应元素在窗口内位置j
5,移动左右指针,将右指针对应元素替换窗口上一个左指针对应元素
6,剩下的就是排序的思路,向左移动或者向右移动,直到有序
func medianSlidingWindow(nums []int, k int) []float64 {
var mid []float64
win:=make([]int,k)
for i:=0;i
win[i]=nums[i]
for j:=i;j>0;j--{
if win[j]
win[j],win[j-1]=win[j-1],win[j]
}else{
break;
}
}
}
mid=append(mid,midd(win))
for i:=k;i<=len(nums)-1;i++{
win=window(win,nums[i],nums[i-k])
mid=append(mid,midd(win))
}
return mid
}
func window(nums []int,val int,last int)[]int{
j:=0
for ;j
if nums[j]==last{
break;
}
}
nums[j]=val
for i:=j;i>0;i--{
if nums[i-1]>nums[i]{
nums[i-1],nums[i]=nums[i],nums[i-1]
}else{
break
}
}
for i:=j;i
if nums[i]>nums[i+1]{
nums[i],nums[i+1]=nums[i+1],nums[i]
}else{
break
}
}
return nums
}
func midd(n []int)float64{
fmt.Println(n)
if len(n)%2!=0{
return float64(n[len(n)/2])
}
return float64(n[len(n)/2]+n[len(n)/2-1])/2.0
}
看完了这篇文章,相信你对"leetcode如何找出滑动窗口中位数"有了一定的了解,如果想了解更多相关知识,欢迎关注行业资讯频道,感谢各位的阅读!
中位数
元素
移动
指针
数组
排序
有序
个数
位置
大小
序列
思路
篇文章
合法
两个
任务
偶数
完了
就是
平均数
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
衡阳县网络安全工作重点
sql 删除数据库日志
软件开发大数据的基础知识
一个数据库有多个表空间
诛仙3怎么查服务器
2017年网络安全时间
用友数据库查看用户名
腾讯云一个人买几个服务器
湖州电脑软件开发教程
魔兽世界找不到玛法里奥服务器
搜索数据库软件有哪些
数据库中like和=的区别
沈阳哪个学校可以学网络安全
节能减排软件开发
自己电脑上搭建服务器
广东综合软件开发直销价格
扫号 数据库
我的世界魔塔服务器武器排行
徐州加工软件开发注意事项
网络安全意识教育培训
数据库的网址
软件开发做哪方面越老越吃香
南京定牛互联网科技有限公司
哪里有剑灵捏脸数据库
智联招聘数据库下载
广东综合软件开发直销价格
大石桥app软件开发
网络安全涉及到哪五个层次结构
数据库open for含义
软件开发专科专业学校排名