python solution O(nlogk)


  • 0
    D
    class Solution(object):
        def medianSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[float]
            """
            import bisect
            
            def index(a, x):
                'Locate the leftmost value exactly equal to x'
                i = bisect.bisect_left(a, x)
                if i != len(a) and a[i] == x:
                    return i
                raise ValueError
    
            rlen = len(nums) - k + 1
            ret = list()
            is_even = False
            w = sorted(nums[0:k])
            if k % 2 == 0 :
                is_even = True
                ret.append(float((w[k/2 - 1] + w[k/2])/2.0))
            else:
                ret.append(float(w[k/2]))
                
            i = 0;
            while i < rlen - 1:
                idx = index(w, nums[i])
                w.pop(idx)
                bisect.insort(w, nums[i+k])
                if is_even :
                   ret.append(float((w[k/2 - 1] + w[k/2])/2.0))
                else:
                   ret.append(float(w[k/2]))
                i = i + 1
            return ret
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.