问题 "Find Median from Data Stream" 我的代码有什么错误？

Question

最近 2 小时我一直在努力解决 LeetCode 上的问题 Find Median from Data Stream，但找不到我代码中的错误。

我的算法是放两个优先级队列，第一个是max-priority queue，存放小于median的元素，第二个是min-priority queue，存放大于median的元素.

这是我的代码：

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(x<num){
                max.push(num);
            }else{
                min.push(num);
                max.push(min.top());
                min.pop();
            }
            maxSize++;
        }else if(minSize < maxSize){
            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(minSize<maxSize)return max.top();
        else return (double(min.top()+max.top())/2);
    }
};

对于以下数字一一给出的输入，在将每个数字作为输入后应输出这些数字的中位数，我得到了不正确的输出。

数字流：

6, 10, 2, 6, 5,  0, 6,  3, 1,  0, 0

我的输出：

6, 8,  6, 6, 6,5.5, 6,  6, 6,5.5, 5

预期输出：

6, 8,  6, 6, 6,5.5, 6,5.5, 5,  4, 3

Answer 1

由于 Jerry Jeremiah 评论了代码的问题，

在行中，if(x>num)min.push(x); 您完全忽略了 num 并将 x 推入队列。您必须更改它，您的代码才会被接受。

问题 "Find Median from Data Stream" 我的代码有什么错误？

What is the mistake in my code for the problem "Find Median from Data Stream"?

c++

sorting

algorithm

priority-queue

data-structures