【排序算法运用】剑指 Offer 41. 数据流中的中位数-跟着帅地玩副业，开拓第二曲线PlayOffer

hi 普通 2023年11月7日上午10:56

对顶堆处理中位数

class MedianFinder {
public:

    priority_queue<int> maxpq; //大根堆放比中位数小的数
    priority_queue<int, vector<int>, greater<int>> minpq; //小根堆放比中位数大的数

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

    }
    //元素先直接加入大根堆，再进行判断调整，看它到底应该在哪个堆
    void addNum(int num) {
        maxpq.push(num);

        if(minpq.size() && maxpq.top() > minpq.top()){
            auto maxt = maxpq.top(), mint = minpq.top();
            maxpq.pop(), minpq.pop() ;
            maxpq.push(mint), minpq.push(maxt);
        }
        if(maxpq.size() > minpq.size() + 1){
            minpq.push(maxpq.top());
            maxpq.pop();
        }

    }
    //那么中位数就是大根堆堆顶元素或两个堆的堆顶元素的平均数
    double findMedian() {
        if(minpq.size() + maxpq.size() & 1) return maxpq.top();
        return (maxpq.top() + minpq.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();
 */

0 赞同 0 条回复

June 普通 2023年9月11日下午11:17

class MedianFinder {

    PriorityQueue<Integer> MinQue;
    PriorityQueue<Integer> MaxQue;

    /** initialize your data structure here. */
    public MedianFinder() {
        MaxQue = new PriorityQueue<Integer>((a, b) -> (b - a)); //大根堆
        MinQue = new PriorityQueue<Integer>((a, b) -> (a - b));
    }

    public void addNum(int num) {
        if(MaxQue.size() == 0)
            MaxQue.add(num);
        else if (MinQue.size() == MaxQue.size())
        {
            if(num > MinQue.peek())
            {
                MaxQue.add(MinQue.poll());
                MinQue.add(num);
            }
            else
            {
                MaxQue.add(num);
            }
        }
        else if(MinQue.size() < MaxQue.size())
        {
             if(num < MaxQue.peek())
            {
                int tmp = MaxQue.poll();
                MinQue.add(tmp);
                MaxQue.add(num);
            }
            else
            {
                MinQue.add(num);
            }
        }
    }

    public double findMedian() {
        if(MaxQue.size() == MinQue.size())
        {
            int maxn = MinQue.peek();
            int minn = MaxQue.peek();
            return (maxn + minn) / 2.0;
        }
        else
        {
            return MaxQue.peek();
        }
    }
}

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

0 赞同 0 条回复

Marshan 普通 2023年8月19日下午3:47

class MedianFinder {
public:
    //保证大跟堆是数据流中小的数字,小根堆是数据流中大的数字,且大根堆和小根堆的大小有特定关系
    priority_queue<int> bigRoot;
    priority_queue<int,vector<int>,greater<int>> littleRoot;

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

    }

    void addNum(int num) {
        if(bigRoot.empty() || num <= bigRoot.top()){
            bigRoot.push(num);
        }
        else{
            littleRoot.push(num);
        }
        if(bigRoot.size() > littleRoot.size() + 1){
            littleRoot.push(bigRoot.top());
            bigRoot.pop();
        }
        if(littleRoot.size() > bigRoot.size()){
            bigRoot.push(littleRoot.top());
            littleRoot.pop();
        }
    }

    double findMedian() {
        int len = littleRoot.size() + bigRoot.size();
        if(len % 2 == 0){
            return (double)(bigRoot.top() + littleRoot.top()) / 2;
        }
        else{
            return (double)(bigRoot.top());
        }
    }
};

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

0 赞同 0 条回复

普通 2023年8月17日下午11:05

c++ 代码
class MedianFinder {
public:
// 最大堆，存储左边一半的数据，堆顶为最大值
priority_queue<int, vector, less> maxHeap;
// 最小堆，存储右边一半的数据，堆顶为最小值
priority_queue<int, vector, greater> minHeap;
/** initialize your data structure here. */
MedianFinder() {
}

// 维持堆数据平衡，并保证左边堆的最大值小于或等于右边堆的最小值
void addNum(int num) {
    /*
     * 当两堆的数据个数相等时候，左边堆添加元素。
     * 采用的方法不是直接将数据插入左边堆，而是将数据先插入右边堆，算法调整后
     * 将堆顶的数据插入到左边堆，这样保证左边堆插入的元素始终是右边堆的最小值。
     * 同理左边数据多，往右边堆添加数据的时候，先将数据放入左边堆，选出最大值放到右边堆中。
     */
    if (maxHeap.size() == minHeap.size()) {
        minHeap.push(num);
        int top = minHeap.top();
        minHeap.pop();
        maxHeap.push(top);
    } else {
        maxHeap.push(num);
        int top = maxHeap.top();
        maxHeap.pop();
        minHeap.push(top);
    }
}

double findMedian() {
    if (maxHeap.size() == minHeap.size()) {
        return (maxHeap.top()+minHeap.top())*1.0/2;
    } else {
        return maxHeap.top()*1.0;
    }
}

};

0 赞同 0 条回复

Mby 普通 2023年8月13日下午10:04

class MedianFinder {

    Queue<Integer> min,max;
    /** initialize your data structure here. */
    public MedianFinder() {
        min = new PriorityQueue<>();//小根，保存较大的
        max = new PriorityQueue<>((x,y) -> (y - x));//大根
    }

    public void addNum(int num) {
        //如果是偶数
        if(min.size() == max.size()){
            min.add(num);
            max.add(min.poll());
        }else{
            max.add(num);
            min.add(max.poll());
        }
    }

    public double findMedian() {
        //如果是偶数
        if(min.size() == max.size()){
            return(min.peek() + max.peek()) / 2.0;
        }else{
            return max.peek() * 1.0;
            //时间复杂度：1.查找中位数O(1) 2.插入元素：O(logn)
            //空间复杂度：O(n)
        }
    }
}

0 赞同 0 条回复

北辰普通 2023年8月8日下午4:30

class MedianFinder {

    Queue<Integer> min,max;

    /** initialize your data structure here. */
    public MedianFinder() {
        max = new PriorityQueue<Integer>((x,y)->(y-x));
        min = new PriorityQueue<Integer>();
    }

    public void addNum(int num) {
        //目前已经加入元素的数目为偶数
        if(min.size()==max.size()){
            min.add(num);
            max.add(min.poll());
        }else{
            max.add(num);
            min.add(max.poll());
        }
    }

    public double findMedian() {
        if(min.size()==max.size()){
           return (min.peek()+max.peek())*1.0/2;
        }else{
            return max.peek()*1.0;
        }
    }
}

0 赞同 0 条回复

#00456B 普通 2023年8月6日上午2:14

class MedianFinder {
public:
    priority_queue<double> minque;//默认是大根堆，用大根堆来维护后半部分最小的数
    priority_queue<double,vector<double>,greater<double>> maxque;//用小根堆来维护前半部分最大的数
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        //默认让大根堆比小根堆多一个
        //当前为偶数个时，让元素先加入小根堆，再把小根堆的top移到大根堆中，实现动态维护。例如[1,2,3][4,5,6]，插入7。先变成[1,2,3][4,5,6,7]，再把4移到前面的大根堆，[1,2,3,4][5,6,7]。
        if(minque.size() == maxque.size()){
            maxque.push(num);
            minque.push(maxque.top());
            maxque.pop();
        }
        else{
            minque.push(num);
            maxque.push(minque.top());
            minque.pop();
        }
    }

    double findMedian() {
        if(minque.size() == maxque.size()){
            return (minque.top() + maxque.top()) / 2;
        }
        else{
            return minque.top();
        }
    }
};

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

0 赞同 0 条回复

NullPointerException 普通 2023年8月4日下午5:02

class MedianFinder {//优先队列自动维护一个单调队列
PriorityQueue queMin;
PriorityQueue queMax;

public MedianFinder() {
    queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
    queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
}

public void addNum(int num) {
    if (queMin.isEmpty() || num <= queMin.peek()) {
        queMin.offer(num);
        if (queMax.size() + 1 < queMin.size()) {
            queMax.offer(queMin.poll());
        }
    } else {
        queMax.offer(num);
        if (queMax.size() > queMin.size()) {
            queMin.offer(queMax.poll());
        }
    }
}

public double findMedian() {
    if (queMin.size() > queMax.size()) {
        return queMin.peek();
    }
    return (queMin.peek() + queMax.peek()) / 2.0;
}

}

0 赞同 0 条回复

AD钙奶普通 2023年8月2日下午2:47

想不出来，看题解看懂了，用两个堆的栈顶元素控制中位数。难点在于在动态数组中添加元素要怎么添加。

class MedianFinder {
    Queue<Integer> minHeap,maxHeap;
    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>((o1,o2) -> o2 - o1);
    }

    public void addNum(int num) {
        if(minHeap.size() != maxHeap.size()) {
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
        } else {
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
        }
    }

    public double findMedian() {
        return minHeap.size() != maxHeap.size() ? minHeap.peek() : (minHeap.peek() + maxHeap.peek()) / 2.0;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月1日下午8:50

class MedianFinder {
    // 输入：
    //["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
    //[[],[1],[2],[],[3],[]]
    //输出：[null,null,null,1.50000,null,2.00000]
    private List<Integer> curList;

    /** initialize your data structure here. */
    public MedianFinder() {
        curList = new ArrayList<>();
    }

    public void addNum(int num) {
        curList.add(num);
    }

    public double findMedian() {
        Integer[] array = curList.toArray(new Integer[curList.size()]);
        Arrays.sort(array);
        int length = array.length;
        if ((length%2)==0) {
            int last = length / 2;
            int start = last-1;
            return (double)(array[start]+array[last])/2;
        } else {
            return (double)array[length/2];
        }
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月1日下午8:37

class MedianFinder {
    private PriorityQueue<Integer> small;
    private PriorityQueue<Integer> large;


    /** initialize your data structure here. */
    public MedianFinder() {
        //大顶堆：保存较小的一半
        small = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        //小顶堆：保存较大的一半
        large = new PriorityQueue<>();
    }

    /**
    为了保证large堆整体大于small堆，想要往 large 里添加元素，不能直接添加，而是要先往 small 里添加，然后再把 small 的堆顶元素加到 large 中；向  small 中添加元素同理。

    为什么呢?

    假设我们准备向 large 中插入元素：

    如果插入的 num 小于 small 的堆顶元素，那么 num 就会留在 small 堆里，为了保证两个堆的元素数量之差不大于 1，作为交换，把 small 堆顶部的元素再插到 large 堆里。

    如果插入的 num 大于 small 的堆顶元素，那么 num 就会成为 samll 的堆顶元素，最后还是会被插入 large 堆中。

    反之，向 small 中插入元素是一个道理，这样就巧妙地保证了 large 堆整体大于 small 堆，且两个堆的元素之差不超过 1，那么中位数就可以通过两个堆的堆顶元素快速计算了。
     */
    public void addNum(int num) {
        if(small.size() >= large.size()){
            small.offer(num);
            large.offer(small.poll());
        }else{
            large.offer(num);
            small.offer(large.poll());
        }
    }


    /**
        如果两个堆元素个数不等，元素个数多的堆的堆顶元素即为中位数；
        如果相等，两个堆顶元素的平均数即为中位数
     */
    public double findMedian() {
        if(large.size() > small.size()){
            return large.peek();
        }else if(small.size() > large.size()){
            return small.peek();
        }else{
            return (small.peek() + large.peek()) / 2.0;
        }
    }
}

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

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月1日下午8:10

8.1
Day23：下面是代码

class MedianFinder {
    Queue<Integer> A, B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>(); //小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x));//大顶堆
    }

    public void addNum(int num) {
        if(A.size() != B.size()){
            A.add(num);
            B.add(A.poll());
        }else{
            B.add(num);
            A.add(B.poll());
        }
    }

    public double findMedian() {
        //注意是/2.0,因为两正数相加除二可能得一个浮点数
        return A.size() == B.size() ? (A.peek() + B.peek()) / 2.0 : A.peek();
    }
}

0 赞同 0 条回复

【排序算法运用】剑指 Offer 41. 数据流中的中位数

共以下 12 个回答

# 回答此问题取消回复

【排序算法运用】剑指 Offer 41. 数据流中的中位数

共以下 12 个回答

# 回答此问题 取消回复

# 回答此问题取消回复