问题描述

  1. 给定一个数组，以及一个窗口，求出窗口中的数字的中位数
  2. https://leetcode-cn.com/problems/sliding-window-median/

怎么求中位数

  1. 插入排序法
    • 用一个 arraylist 存储窗口内的数字
    • 每次去掉窗口尾的一个数据，并按照插入排序的规则将新的数据插入 arraylist 中。
    • 在一个有序数组中计算中位数就很简单了。
    • 可以用二分查找进行优化。
  2. 时间复杂度
    • 未经优化 $O(nk)
    • 二分查找优化 $(nlogk)$