leetcode-cn 2021年1月 2021年2月 每日一题

算法之美
21

480. 滑动窗口中位数

难度困难152

中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

  • [2,3,4]，中位数是 3
  • [2,3]，中位数是 (2 + 3) / 2 = 2.5

给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

/*
 * @Author: kingeasternsun
 * @Date: 2021-02-03 09:02:46
 * @LastEditTime: 2021-02-03 09:40:16
 * @LastEditors: kingeasternsun
 * @Description: In User Settings Edit
 * @FilePath: \490medianSlidingWindow\490.go
 */
package leetcode

import "sort"

func medianSlidingWindow(nums []int, k int) []float64 {
	if k > len(nums) {
		return nil
	}

	if k == 0 {
		return nil
	}
	res := []float64{}

	if k == 1 {
		for _, v := range nums {
			res = append(res, float64(v))
		}
		return res
	}

	winNums := make([]int, k) //维护一个有序的滑动窗口就可以了
	copy(winNums, nums[:k])
	sort.Ints(winNums)

	res = append(res, getMedian(winNums, k))
	for i := k; i < len(nums); i++ {
		id := sort.SearchInts(winNums, nums[i-k]) //移除i-k这个数字
		winNums[id] = nums[i]                     //加入 i上的数字

		//调整winNum[id]的数字位置，让winNums保持有序
		for id < k-1 && winNums[id] > winNums[id+1] {
			winNums[id], winNums[id+1] = winNums[id+1], winNums[id]
			id++
		}

		for id > 0 && winNums[id] < winNums[id-1] {
			winNums[id], winNums[id-1] = winNums[id-1], winNums[id]
			id--
		}

		res = append(res, getMedian(winNums, k))
	}
	return res
}

func getMedian(winNums []int, k int) float64 {
	return (float64(winNums[k/2]) + float64(winNums[(k-1)/2])) / 2
}