Ref: https://leetcode-cn.com/problems/sliding-window-median/
這道題主要有兩種思路解決豆胸，一是一開始想到的數(shù)組暴力法，二是利用二分查找思想實現(xiàn)時間復(fù)雜度的方法预愤。
首先殴泰，對于一個有序數(shù)組五督，計算中位數(shù)可以采用下述實現(xiàn)：
median = lambda a: (a[(len(a) - 1) // 2] + a[len(a) // 2]) / 2
數(shù)組暴力法
使用數(shù)組暴力法押逼，控制窗口滑動箫措，并對窗口內(nèi)序列進行排序塑陵，進而計算中位數(shù)并存入最終結(jié)果爱态，代碼如下：
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
由于進行了次排序谭贪，因此時間復(fù)雜度為
。
數(shù)組二分法
使用數(shù)組二分法锦担，主要思路如下：
對于測試用例：
nums = [1, 3, -1, -3, 5]
k = 2
- 初始化前
個元素的數(shù)組
俭识，排序，計算中位數(shù)放入result洞渔，之后在此基礎(chǔ)上進行如下操作滑動窗口（窗口大小
，左邊界為
磁椒，右邊界為
）：
-
向左滑動堤瘤，移除左邊界
浆熔，為保持?jǐn)?shù)組
有序性本辐，采用二分查找刪除和插入，其中pop和insert時間復(fù)雜度為
医增，二分查找為
慎皱，得到
；
- 同理叶骨，
茫多；
- 同理，
忽刽；
- 最后天揖，
。
-
- 為方便起見直接調(diào)用了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
因此歉甚，全部算法代碼實現(xiàn)如下：
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
