小编给大家分享一下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 []float64win:=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:=0for ;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如何找出滑动窗口中位数”有了一定的了解，如果想了解更多相关知识，欢迎关注亿速云行业资讯频道，感谢各位的阅读！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
