leetcode480 Sliding Window Median

 1 """
 2 Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
 3 Examples:
 4 [2,3,4] , the median is 3
 5 [2,3], the median is (2 + 3) / 2 = 2.5
 6 Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.
 7 For example,
 8 Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
 9 Window position                Median
10 ---------------               -----
11 [1  3  -1] -3  5  3  6  7       1
12  1 [3  -1  -3] 5  3  6  7       -1
13  1  3 [-1  -3  5] 3  6  7       -1
14  1  3  -1 [-3  5  3] 6  7       3
15  1  3  -1  -3 [5  3  6] 7       5
16  1  3  -1  -3  5 [3  6  7]      6
17 Therefore, return the median sliding window as [1,-1,-1,3,5,6].
18 """
19 """
20 用大小为k的滑动窗口，计算每个窗口的中位数
21 用二分排序来维护window的有序性，用到了bisect
22 具体做法时找到nums[i-k]元素的位置并弹出
23 插入num[i]元素到正确的位置，保证window有序，计算中位数
24 """
25 class Solution1:
26     def medianSlidingWindow(self, nums, k):
27         import bisect
28         if k == 0:
29             return []
30         win = sorted(nums[:k])
31         ans = []
32         for i in range(k, len(nums) + 1):
33             median = (win[k // 2] + win[(k - 1) // 2]) / 2.0#win的长度奇偶求平均值通用
34             ans.append(median)
35             if i == len(nums):
36                 break
37             # get the index of the nums[i-k] and then delete it, then insort nums[i]
38             index = bisect.bisect_left(win, nums[i - k])
39             win.pop(index)
40             bisect.insort_left(win, nums[i])
41             """
42             L = [1,3,4,6,8]
43             x = 3
44             x_insert_point = bisect.bisect_left(L,x)　　1
45             #在L中查找x，x存在时返回x左侧的位置，x不存在返回应该插入的位置
46             这是3存在于列表中，返回左侧位置１
47             x_insert_point = bisect.bisect_right(L,x)   3
48             #在L中查找x，x存在时返回x右侧的位置，x不存在返回应该插入的位置
49             这是3存在于列表中，返回右侧位置３
50             x_insort_left = bisect.insort_left(L,x)  [1, 3, 3, 4, 6, 8]
51             #将x插入到列表L中，x存在时插入在左侧，x不存在时插入正确位置
52             x_insort_rigth = bisect.insort_right(L,x)  [1, 3, 3, 3, 4, 6, 8]
53             #将x插入到列表L中，x存在时插入在右侧，x不存在时插入正确位置
54             """
55         return ans
56 
57 """
58 [1,3,-1,-3,5,3,6,7]
59 3
60 Output
61 [1.00000,-1.00000,-1.00000,3.00000,5.00000]
62 Expected
63 [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
64 """
65 """
66 精通python的写法
67 """
68 class Solution2:
69     def medianSlidingWindow(self, nums, k):
70         import bisect
71         window = sorted(nums[:k])
72         medians = []
73         for a, b in zip(nums, nums[k:]+[0]):# 如果不加0，答案就少一个值,如上所示，zip返回的是一个tuple(a, b)
74             medians.append((window[k//2] + window[(k-1)//2]) / 2.)
75             window.remove(a)
76             bisect.insort(window, b)
77         return medians