小编给大家分享一下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<k;i++{ win[i]=nums[i] for j:=i;j>0;j--{ if win[j]<win[j-1]{ 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<len(nums);j++{ if nums[j]==last{ break; } } nums[j]=valfor 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<len(nums)-1;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如何找出滑动窗口中位数”有了一定的了解，如果想了解更多相关知识，欢迎关注亿速云行业资讯频道，感谢各位的阅读！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4586289/blog/4634816
