480. Sliding Window Median

Ref: https://leetcode-cn.com/problems/sliding-window-median/

这道题主要有两种思路解决，一是一开始想到的数组暴力法，二是利用二分查找思想实现时间复杂度的方法。
首先，对于一个有序数组，计算中位数可以采用下述实现：

median = lambda a: (a[(len(a) - 1) // 2] + a[len(a) // 2]) / 2

数组暴力法

使用数组暴力法，控制窗口滑动，并对窗口内序列进行排序，进而计算中位数并存入最终结果，代码如下：

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        median = lambda a: (a[(len(a)-1)//2] + a[len(a)//2]) / 2
        res = []
        for i in range(len(nums)-k+1):
            res.append(median(sorted(nums[i:i+k])))
        return res

由于进行了次排序，因此时间复杂度为。

数组二分法

使用数组二分法，主要思路如下：

对于测试用例：

nums = [1, 3, -1, -3, 5]
k = 2

• 初始化前个元素的数组，排序，计算中位数放入result，之后在此基础上进行如下操作滑动窗口（窗口大小，步长为，左边界为，右边界为）：
  1. 向左滑动，移除左边界上的元素，增加右边界上的元素，为保持数组有序性，采用二分查找删除和插入，其中pop和insert时间复杂度为，二分查找为，得到；
  2. 同理，；
  3. 同理，；
  4. 最后，。
• 为方便起见直接调用了Python的bisect库，事实上查阅其源代码，这里也可以自己写出二分查找算法，代码如下：

   def find(self, a, value):
       lo = 0
       hi = len(a)
       while lo < hi:
           mid = (lo + hi) // 2
           if a[mid] < value:
               lo = mid + 1
           else:
               hi = mid
       return lo

因此，全部算法代码实现如下：

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        median = lambda x: (x[(len(x) - 1) // 2] + x[len(x) // 2]) / 2
        a = nums[:k]
        a.sort()
        result = [median(a)]
        for i, j in zip(nums[:-k], nums[k:]):
            a.pop(bisect.bisect_left(a, i))
            a.insert(bisect.bisect_left(a, j), j)
            result.append(median(a))
        return result