How to find the median of sliding window by leetcode

Xiaobian to share with you how leetcode to find the median number of sliding windows, I hope you have something to gain after reading this article, let's discuss it together!

The median is the number in the middle of an ordered sequence. If the size of the sequence is even, then there is no middle number; the median is the average of the two middle numbers.

For example:

[2, 3, 4], median is 3

[2,3], median is (2 + 3) / 2 = 2.5

Given an array of numbers, there is a window of size k that slides from the far left to the far right. There are k numbers in the window, and each time the window moves 1 bit. Your task is to find the median of the elements in the new window you get after each window move and output an array of them.

For example:

Given nums = [1,3,-1,-3,5,3,6,7] and k = 3.

window position median

--------------- -----

[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

Therefore, return the median array [1,-1,-1, 3, 5, 6] of this sliding window.

Tip:

Suppose k is legal, i.e. k is always less than the number of elements in the input nonempty array.

Solution:

1. Note that the median is the median of the sorted data within the window.

2. For the interior of the window, the idea of insertion sorting can be used for sorting.

3. Initially, insert the first k values into the window.

4, find the left pointer corresponding to the element in the window position j

5. Move the left and right pointers and replace the corresponding elements of the right pointer with the corresponding elements of the left pointer on the window.

6. The rest is the sort of idea, moving left or right, until it's ordered.

func medianSlidingWindow(nums []int, k int) []float64 { var mid []float64 win:=make([]int,k) for i:=0;i0;j--{ if win[j]