绵阳梓潼网站制作公司

leetcode如何找出滑动窗口中位数

小编给大家分享一下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://myzitong.com/article/jihdgh.html

其他资讯