Median in data stream

Title Description

How to get the median in a data stream? If an odd number is read from the data stream, the median is the number in the middle after all the numbers are sorted. If even numbers are read from the data stream, the median is the average of the middle two numbers after all the numbers are sorted. We use the Insert() method to read the data stream and the getmedia () method to get the median of the currently read data.

link

https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=11216&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

Code

class Solution {
public:
	vector<int> max;  // Maximum, large top reactor 
	vector<int> min;  // Minimum, small top reactor 
    void Insert(int num)
    {
    	int len = max.size() + min.size();
        if(len%2 == 0){  // There are even data at present, insert the current data into the small top heap
        	if(min.size() > 0 && num > min[0]){
        		int temp = min[0];
        		min.push_back(num);
        		pop_heap(min.begin(),min.end(),greater<int>());
        		max.push_back(temp);
        		push_heap(max.begin(),max.end(),less<int>());
        		min.pop_back();
        	} 
        	else{
        		max.push_back(num);
        		push_heap(max.begin(),max.end(),less<int>());
        	}
        }
        else{
        	if(max.size() > 0 && num < max[0]){
        		int temp = max[0];
        		max.push_back(num);
        		pop_heap(max.begin(),max.end(),less<int>());
        		min.push_back(temp);
        		push_heap(min.begin(),min.end(),greater<int>());
        		max.pop_back();
        	}
        	else{
        		min.push_back(num);
        		push_heap(min.begin(),min.end(),greater<int>());
        	}
        }
    }

    double GetMedian()
    { 
    	int len = max.size() + min.size();
    	if(len <= 0){
    		return 0;
    	}
    	if(len%2 == 0){
    		return ((max[0] + min[0]) / 2.0);
    	}
    	else{
    		return max[0];
    	}
    }
};

Tags: less

Posted on Sun, 01 Dec 2019 18:01:09 -0800 by FramezArt