LeetCode295. Find Median from Data Stream(검지 offer 41번)

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.
For example, [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.
Example:
addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2
Follow up:
If all integer numbers from the stream are between 0 and 100, how would you optimize it? If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

법일

stl 우선 대기열 두 개를 엽니다. - maxheap.small은 앞의 절반, lage는 뒤의 절반을 넣는다.그들의 순서를 어릴 때부터 지금까지 변하지 않게 하기 위해small은 원수로 저장하고large는 마이너스로 저장한다.O(logn) 추가 삭제, O(1) 세부 정보 찾기: 1.홀수 크기라면small.top ()는 요청한 중위수입니다.짝수인 경우 (small.top () -large.top ()/2는 중위수입니다. 빼든지 말든지.우선 대기열의 유형은 롱입니다. -2^31 (which negated is itself, when using 32-bit ints), I use integer types larger than 32 bits. 3.(small.top()-large.top())/2.0.2.0으로 나누지 않으면 정수로 되돌아옵니다

class MedianFinder {
private:
 std::priority_queue<long> small,large;
    
public:
    /** initialize your data structure here. */
    MedianFinder() {
          }
    
    void addNum(int num) {
        small.push(num);//O(logn)

        large.push(-small.top());//O(logn)
        small.pop();//O(logn)

        // small large 
        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;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

법2

두 stl의 우선 대기열을 엽니다. -maxheap과minheap은 앞뒤 절반의 세부 사항을 저장합니다.만약num이maxheap보다 작다면top (),num 작은 절반에 최대 무더기를 넣는 것을 설명합니다. 그렇지 않으면 정렬에 실패할 수 있습니다.2.maxheap이 영원히minheap의 수량보다 크거나 같다고 가정하면 두 무더기가 같으면 평균값이다.같지 않으면 maxheap.top 3.AVL의 사상을 이용하여 두 무더기의 깊이의 차이가 1을 초과하지 않도록 보증하며, 1을 초과하면 max더미를min더미에 넣는다

class MedianFinder {
private:
	priority_queue<long> maxheap;
	priority_queue<long, vector<long>, greater<long>> minheap;

public:
	/** initialize your data structure here. */
	MedianFinder() {
	}

	void addNum(int num) {
		// ： num maxheap.top(), num ， ， ， 。
		if (maxheap.size() == 0 || num < maxheap.top())
		{
			maxheap.push(num);
		}
		else
			minheap.push(num);
		// 
        if (minheap.size()> maxheap.size())
		{
			maxheap.push(minheap.top());
			minheap.pop();
		}
        else if (maxheap.size()>1 + minheap.size())
		{
			minheap.push(maxheap.top());
			maxheap.pop();
		}  
	}

	double findMedian() {
		return maxheap.size()>minheap.size() ? maxheap.top() : (maxheap.top() + minheap.top()) / 2.0;
	}
};