Data Stream Median

Question

Numbers keep coming, return the median of numbers at every time a new number added.

Have you met this question in a real interview? Yes Example

For numbers coming list: [1, 2, 3, 4, 5], return [1, 1, 2, 2, 3].

For numbers coming list: [4, 5, 1, 3, 2, 6, 0], return [4, 4, 4, 3, 3, 3, 3].

For numbers coming list: [2, 20, 100], return [2, 2, 20].

Challenge Total run time in O(nlogn).

Thoughts

python heapq都是minheap,我们可以将 值 * -1， 放进去

Solution

from heapq import *
class Solution:
    """
    @param nums: A list of integers.
    @return: The median of numbers
    """
    def medianII(self, nums):
        # write your code here
        if not nums:
            return []
        result = []
        minHeap = []
        maxHeap = []
        median = nums[0]
        result.append(median)
        for idx, num in enumerate(nums):
            if idx == 0:
                continue

            if num > median:
                heappush(minHeap, num)
            else:
                heappush(maxHeap, -num)

            while len(maxHeap) > len(minHeap):
                heappush(minHeap, median)
                median = heappop(maxHeap) * -1

            while len(minHeap) > len(maxHeap) + 1:
                heappush(maxHeap, -median)
                median = heappop(minHeap)

            result.append(median)

        return result