Leetcode 480.滑动窗口中位数

Posted on |

480.滑动窗口中位数

题目

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

例如：

[2,3,4]，中位数是 3

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
例如：

给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。

窗口位置                      中位数
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6
 因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。

提示：
假设k是合法的，即：k 始终小于输入的非空数组的元素个数.

方法1:Python 二分查找和插入模块bisect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def medianSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[float]
        """
        import bisect
        if k == 1:
            return map(float,nums)

        self.window = nums[0:k]
        self.window.sort()
        ret = []
        ret.append(self.getCenter(k))

        i = 1
        j = k
        while j < len(nums):
            self.window.remove(nums[i-1])
            bisect.insort_left(self.window, nums[j])
            ret.append(self.getCenter(k))
            j += 1
            i += 1
        return ret



    def getCenter(self, k):
        if k % 2 == 0:
            return float((self.window[k//2] + self.window[k//2-1]) / 2.0)
        else:
            return float(self.window[k//2])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def medianSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[float]
        """
        median=[]
        window=sorted(nums[:k])
        median.append((window[k/2]+window[k/2-(k&1==0)])/2.)

        for i in range(len(nums)-k):
            window.remove(nums[i])
            bisect.insort(window,nums[i+k])
            median.append((window[k/2]+window[k/2-(k&1==0)])/2.)
        return median

方法二：两个堆

1
2
3
4
5
6
2-heap (min, max) based solution:
uses 2 heaps left-(max)heap lh and right-(min)heap rh. The key idea is the maintain the size invariance of the heaps as we add and remove elements. The top of both the heaps can be used to calculate the median.
- We use lazy-deletion from the heap
- using the first k elements construct a min heap lh. Then pop k-k/2 and add it to the rh. Now the heap sized are set at k/2 and k-k/2
- Iterate over rest of the numbers and add it to the appropriate heap and maintain heap size invariance by moving the top number from one heap to another as needed.
O(N logK) beats 90%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution(object):
    def medianSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[float]
        """
        from heapq import *
        lh,rh,res=[],[],[]

        # 初始化
        for i,n in enumerate(nums[:k]):
            heappush(lh,(-n,i))
        for i in range(k-k//2):
            heappush(rh,(-lh[0][0],lh[0][1]))
            heappop(lh)

        for i,n in enumerate(nums[k:]):
            res.append(rh[0][0]/1. if k&1 else (rh[0][0]-lh[0][0])/2.)
            # 新增加元素nums[i+k]==n，删除元素nums[i]，保持两个堆长度一致
            if n>=rh[0][0]:
                heappush(rh,(n,i+k))
                if nums[i]<=rh[0][0]:
                    heappush(lh,(-rh[0][0],rh[0][1]))
                    heappop(rh)
            else:
                heappush(lh,(-n,i+k))
                if nums[i]>=rh[0][0]:
                    heappush(rh,(-lh[0][0],lh[0][1]))
                    heappop(lh)

            while (lh and lh[0][1]<=i):heappop(lh)
            while (rh and rh[0][1]<=i):heappop(rh)
        res.append(rh[0][0]/1. if k&1 else (rh[0][0]-lh[0][0])/2.)
        return res

较繁琐的代码，但容易理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution(object):
    def medianSlidingWindow(self, nums, k):

    from heapq import heappush, heappop, heapify

    lMaxHeap = []
    # for every pair in heap, not only record the key, but also its position in nums
    firstList = [(nums[i], i) for i in range(k)]
    heapify(firstList)
    rMinHeap = firstList
    if k == 1:
        return [float(i) for i in nums]
    # initialize two heap: size of Right min heap  - size of Left max heap >= 1
    # in the following, abbreviate right min heap as right; left max heap as left
    # when k is odd, left size == right size - 1;
    # when k is even, left size == right size
    while len(rMinHeap) - len(lMaxHeap) >= 2:
        pop = heappop(rMinHeap)
        # implement max heap by key * (-1) in min heap
        heappush(lMaxHeap, ( -1 * pop[0], pop[1]))

    medianList = [float(rMinHeap[0][0]) if k%2 == 1 else float(rMinHeap[0][0] - lMaxHeap[0][0])/2]

    for i in xrange(k, len(nums)):
        # if balance >= 2 -> push(left , pop(right))
        # elif balance <= 2 -> push(left, pop(right))
        balance = 0
        # add cases: when added num greater or equal to right top of min heap, add it to right. \
        # Otherwise, add it to left
        if nums[i] >= rMinHeap[0][0]:
            balance += 1
            heappush(rMinHeap, (nums[i], i))
        else:
            balance -= 1
            heappush(lMaxHeap, (-nums[i], i))
        # remove case:
        # (1) the removing element is in top of either list -> remove until top is in current list
        # at the same time, change balance
        # (2) the removing element is not in both top of heap -> just change balance

        if lMaxHeap[0][1] == i-k:
            heappop(lMaxHeap)
            while (lMaxHeap) and (lMaxHeap[0][1] <= i - k):
                heappop(lMaxHeap)
            balance += 1
        elif rMinHeap[0][1] == i - k:
            heappop(rMinHeap)
            while (rMinHeap) and (rMinHeap[0][1] <= i - k):
                heappop(rMinHeap)
            balance -= 1
        elif rMinHeap[0][0] >= nums[i - k]:
            balance += 1
        else:
            balance -= 1

        #balance num in both heap
        if balance > 0:
            popElement = heappop(rMinHeap)
            heappush(lMaxHeap, (-popElement[0], popElement[1]))
            while (rMinHeap) and (rMinHeap[0][1] <= i - k):
                heappop(rMinHeap)
        elif balance < 0:
            popElement = heappop(lMaxHeap)
            heappush(rMinHeap,(-popElement[0], popElement[1]))
            while (lMaxHeap) and (lMaxHeap[0][1] <= i - k):
                heappop(lMaxHeap)  

        medianList.append(float(rMinHeap[0][0]) if k%2 == 1 else float(rMinHeap[0][0] - lMaxHeap[0][0])/2)


    return medianList

Python

Python 有一个 bisect 模块，用于维护有序列表。bisect 模块实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect 是二分法的意思，这里使用二分法来排序，它会将一个元素插入到一个有序列表的合适位置，这使得不需要每次调用 sort 的方式维护有序列表。

bisect模块采用经典的二分算法查找元素。模块提供下面几个方法：

1
bisect.bisect_left(a, x, lo=0, hi=len(a))

定位x在序列a中的插入点，并保持原来的有序状态不变。参数lo和hi用于指定查找区间。如果x已经存在于a中，那么插入点在已存在元素的左边。函数的返回值是列表的整数下标。

1
bisect.bisect_right(a, x, lo=0, hi=len(a))

和上面的区别是插入点在右边。函数的返回值依然是一个列表下标整数。

1
bisect.bisect(a, x, lo=0, hi=len(a))

等同于

1
2

注意，前面这三个方法都是获取插入位置，也就是列表的某个下标的，并不实际插入。但下面三个方法实际插入元素，没有返回值。

bisect.insort_left(a, x, lo=0, hi=len(a))

1
2

将x插入有序序列a内，并保持有序状态。相当于```a.insert(bisect.bisect_left(a, x, lo, hi), x)```。碰到相同的元素则插入到元素的左边。这个操作通常是 O(log n) 的时间复杂度。

bisect.insort_right(a, x, lo=0, hi=len(a))

1
同上，只不过碰到相同的元素则插入到元素的右边。

bisect.insort(a, x, lo=0, hi=len(a))
等同于insort_right()```。