小編給大家分享一下leetcode如何找出滑動(dòng)窗口中位數(shù)，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡(jiǎn)單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：主機(jī)域名、虛擬空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、牡丹江網(wǎng)站維護(hù)、網(wǎng)站推廣。

中位數(shù)是有序序列最中間的那個(gè)數(shù)。如果序列的大小是偶數(shù)，則沒有最中間的數(shù)；此時(shí)中位數(shù)是最中間的兩個(gè)數(shù)的平均數(shù)。

例如：

[2,3,4]，中位數(shù)是 3

[2,3]，中位數(shù)是 (2 + 3) / 2 = 2.5

給出一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的窗口從最左端滑動(dòng)到最右端。窗口中有 k 個(gè)數(shù)，每次窗口移動(dòng) 1 位。你的任務(wù)是找出每次窗口移動(dòng)后得到的新窗口中元素的中位數(shù)，并輸出由它們組成的數(shù)組。

例如：

給出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。

窗口位置                      中位數(shù)
---------------               -----
[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

 因此，返回該滑動(dòng)窗口的中位數(shù)數(shù)組 [1,-1,-1,3,5,6]。

提示：
假設(shè)k是合法的，即：k 始終小于輸入的非空數(shù)組的元素個(gè)數(shù).

解題思路：

1，注意中位數(shù)是窗口內(nèi)數(shù)據(jù)排序后的中位數(shù)

2，對(duì)于窗口內(nèi)部可以采用插入排序的思想進(jìn)行排序

3，初始時(shí)，采用插入排序，將前k個(gè)值，插入窗口

4，找到左指針對(duì)應(yīng)元素在窗口內(nèi)位置j

5，移動(dòng)左右指針，將右指針對(duì)應(yīng)元素替換窗口上一個(gè)左指針對(duì)應(yīng)元素

6，剩下的就是排序的思路，向左移動(dòng)或者向右移動(dòng)，直到有序

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}

看完了這篇文章，相信你對(duì)“l(fā)eetcode如何找出滑動(dòng)窗口中位數(shù)”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！