小编给大家分享一下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如何找出滑动窗口中位数”有了一定的了解，如果想了解更多相关知识，欢迎关注创新互联行业资讯频道，感谢各位的阅读！
文章题目：leetcode如何找出滑动窗口中位数
文章起源：
http://cdkjz.cn/article/jihdgh.html
