Easy O(nlogk) Python solution using 2 binary searches


  • 0

    The idea is simple: after caching and sorting the first k numbers and get the first median, just continue to:

    • remove the number leaving sliding window from cache; and
    • insert the number entering sliding window into cache and keep it sorted.

    Since the cache is sorted, both steps can be done by binary search.

    class Solution(object):
        def medianSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[float]
            """
            cache = sorted(nums[:k])
            # get first median
            ans = [float(cache[k/2]+cache[~(k/2)])/2]
            for to_remove, to_insert in zip(nums[:len(nums)-k], nums[k:]):
                # remove the number leaving sliding window from cache
                idx = self.binSearchValue(cache, to_remove, 0, k-1)
                del cache[idx]
                # insert the number entering sliding window into cache and keep it sorted
                idx = self.binSearchInterval(cache, to_insert, 0, k-1)
                cache.insert(idx, to_insert)
                # get median
                ans.append(float(cache[k/2]+cache[~(k/2)])/2)
            return ans
    
        def binSearchValue(self, array, val, l, r):
            if l==r:
                return l
            m = (l+r)/2
            if val==array[m]:
                return m
            elif val<array[m]:
                return self.binSearchValue(array, val, l, m-1)
            else:
                return self.binSearchValue(array, val, m+1, r)
        
        def binSearchInterval(self, array, val, l, r):
            """
            I define the index of interval (returned value) as
            array:    [  -2  0  2  ]
            interval:  ↑0  ↑1 ↑2 ↑3
            Extra care is needed when enumerating each case
            """
            if l==r:
                return l
            if l==r-1:
                if val<array[l]:
                    return l
                else:
                    return r
            m = (l+r)/2
            if val>=array[m-1] and val<array[m]:
                return m
            elif val<array[m-1]:
                return self.binSearchInterval(array, val, l, m-1)
            else:
                return self.binSearchInterval(array, val, m+1, r)
    

Log in to reply
 

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