溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
