I'm been struggling to solve the question Find Median from Data Stream on LeetCode for the last 2 hours but couldn't find the mistake in my code.
My algorithm is to put two priority queues, the first one is a max-priority queue which stores the elements less than the median, and the second one is a min-priority queue which stores the elements greater than the median.
This is my code:
struct get_min{
bool operator()(int i, int j){
return i>j;
}
};
class MedianFinder {
//queue which stores elements which are greater than the median
priority_queue<int, vector<int>, get_min> max;
int minSize, maxSize;
//queue which stores elements which are less than the median
priority_queue<int> min;
public:
MedianFinder() {
minSize = 0;
maxSize = 0;
}
void addNum(int num) {
if(minSize>maxSize){
int x = min.top();
if(xelse{
min.push(num);
max.push(min.top());
min.pop();
}
maxSize++;
}else if(minSize < maxSize class="hljs-keyword">int x = max.top();
if(x>num)min.push(x);
else{
max.push(num);
min.push(max.top());
max.pop();
}
minSize++;
}else if(minSize==0 && maxSize==0){
min.push(num);
minSize++;
}else{
int x = min.top();
int y = max.top();
if(num<=x){
min.push(num);
minSize++;
}else{
max.push(num);
maxSize++;
}
}
}
double findMedian() {
if(minSize> maxSize)return min.top();
else if(minSizereturn max.top();
else return (double(min.top()+max.top())/2);
}
};
For the input where the following numbers are given one by one and the median of those numbers should be output after taking each number as input, I'm getting the incorrect output.
Stream of numbers:
6, 10, 2, 6, 5, 0, 6, 3, 1, 0, 0
My output:
6, 8, 6, 6, 6,5.5, 6, 6, 6,5.5, 5
Expected Output:
6, 8, 6, 6, 6,5.5, 6,5.5, 5, 4, 3