c++ - 我的代码中关于“从数据流中查找中位数”问题的错误是什么？

问题描述

在过去的 2 个小时里，我一直在努力解决在 LeetCode 上从数据流中查找中位数的问题，但在我的代码中找不到错误。

我的算法是放两个优先级队列，第一个是最大优先级队列，存储小于中位数的元素，第二个是最小优先级队列，存储大于中位数的元素。

这是我的代码：

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

标签： c++algorithmsortingdata-structurespriority-queue

c++ - 我的代码中关于“从数据流中查找中位数”问题的错误是什么？

问题描述

解决方案

推荐阅读