480.md

480. Sliding Window Median

Solution 1 (time O(n*k), space O(k))

class Solution(object):
    def medianSlidingWindow(self, nums, k):
        n = len(nums)
        ans = []
        window = sorted(nums[:k])
        if k % 2 != 0:
            ans.append(window[k // 2])
        else:
            ans.append((window[k // 2 - 1] + window[k // 2]) / 2.0)
        p1, p2 = 0, k
        while p2 < n:
            window.remove(nums[p1])
            bisect.insort(window, nums[p2])
            if k % 2 != 0:
                ans.append(window[k // 2])
            else:
                ans.append((window[k // 2 - 1] + window[k // 2]) / 2.0)
            p1 += 1
            p2 += 1
        return ans