leetcode Find Median from Data Stream

leetcode Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: [2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.

double findMedian() - Return the median of all elements so far.

For example:

add(1)

add(2)

findMedian() -> 1.5

add(3)

findMedian() -> 2

题目地址： leetcode Find Median from Data Stream

题意：

要求设计一个数据结构，支持实时插入，和实时查询中位数。

思路：

O(n)插入，O(1)查询的方法很简单，直接一个数组，每次插入排序。。。。这里不做介绍。

O(logn)插入，O(1)查询：建立一个最大堆和最小堆，思路是这两个堆顶指向中间的元素，这样可以达到O(1)查询。

最大堆负责存储这些数左边的，最小堆则负责右边的。每次插入时候判断是插入左边还是右边，然后看看是否要平衡一下两个堆的元素个数。

以 1，2，3，4插入为例，最大堆命名为small（因为是左边的元素），最小堆为large

1进来，放进small
轮到2，仍然放进small，但是small的元素比large多2，不平衡，于是取出2放入large
轮到3，3比large的2来得大，直接放入large
轮到4，4比large的2来得大，直接放入large，但是large的元素比small多2，不平衡，于是取出2放入small

查询时，根据个数大小判断应该是返回small还是large的。

个数相等则说明为偶数个，返回均值。

实现上我用了priority_queue，这个是个最大堆，所以右边的（large）插入取相反数。

C++

class MedianFinder {
	priority_queue<int> small, large;
public:
	// Adds a number into the data structure.
	void addNum(int num) {
		if (!large.empty() && -large.top() < num)
			large.push(-num);
		else
			small.push(num);

		if (small.size() - large.size() == 2) {
			large.push(-small.top());
			small.pop();
		}
		else if (small.size() - large.size() == -2) {
			small.push(-large.top());
			large.pop();
		}
	}

	// Returns the median of current data stream
	double findMedian() {
		if (small.size() > large.size()) return small.top();
		else if (small.size() < large.size()) return -large.top();
		return (small.top() - large.top()) / 2.0;
	}
};

看了discuss有比我简单的代码，不过比我慢。毕竟做了无用的push和pop

class MedianFinder {
    priority_queue<long> small, large;
public:

    void addNum(int num) {
        small.push(num);
        large.push(-small.top());
        small.pop();
        if (small.size() < large.size()) {
            small.push(-large.top());
            large.pop();
        }
    }

    double findMedian() {
        return small.size() > large.size()
               ? small.top()
               : (small.top() - large.top()) / 2.0;
    }
};

剑指offer也有这题，下面是我刷《剑指offer》时写的代码

c++

class MedianFinder {
    priority_queue<int> left;
    priority_queue<int> right;
public:
    MedianFinder() {}
    
    void addNum(int num) {
        if (left.empty() || num <= left.top()) {
            left.push(num);
            if (right.size() + 1 < left.size()) {
                int temp = left.top();
                left.pop();
                right.push(-temp);
            }
        } else { // num > left.top()
            right.push(-num);
            if (right.size() > left.size()) {
                int temp = right.top();
                right.pop();
                left.push(-temp);
            }
        }
    }
    
    double findMedian() {
        return (left.size() + right.size()) & 1? left.top() : (left.top() - right.top()) * 0.5;
    }
};

Python

class MedianFinder:
    def __init__(self):
        self.left = []
        self.right = []

    def addNum(self, num: int) -> None:
        if not self.left or -self.left[0] > num:
            heapq.heappush(self.left, -num)
            if len(self.right) + 1 < len(self.left):
                temp = heapq.heappop(self.left)
                heapq.heappush(self.right, -temp)
        else:
            heapq.heappush(self.right, num)
            if len(self.right) > len(self.left):
                temp = heapq.heappop(self.right)
                heapq.heappush(self.left, -temp)

    def findMedian(self) -> float:
        return -self.left[0] if (len(self.left) + len(self.right)) & 1 else (-self.left[0] + self.right[0]) * 0.5