一道求中位数的算法题把我整不会了 :: labuladong的算法小抄

[labuladong]

文章链接点这里：一道求中位数的算法题把我整不会了

评论礼仪 见这里，违者直接拉黑。

[jennyliulfm]

解释 浅显易懂 那个 addNum 的逻辑有点难理解和记忆：
我这么改了一下，首先把第一个num 存到 small heap, 如果当前要添加的元素小于small的堆顶元素 也存到small里面，否则存到large 里面，这样保证了small里面的元素都比large里面的小；step2: 调整heap 的元素；如果元素之差多余1 就去调整元素，把元素多的堆顶元素放到元素少的堆里面。具体实现如下：

 public void addNum(int num) {
        if(small.size() == 0 || num < small.peek()) {
            small.offer(num);
        } else {
            large.offer(num);
        }
        
        if(Math.abs(large.size() - small.size()) > 1)
        {
            if(large.size() > small.size()) {
                small.offer(large.poll());
            }else {
                large.offer(small.poll());
            }
        }
    }

自己根据思路写的时候 犯的错误是
return (small.peek() + large.peek()) / 2.0 ;

写成了
return (small.peek() + large.peek()) / 2 ;

[5Reeson]

这个很好理解、记忆！

[bruceeewong]

貌似运行时间还快了2333

[JY-5]

博主的字体有点不容易阅读诶，建议加粗字体，行间距可能也可以加大。谢谢啦！

[Lock0nStratos]

python 版本，heapq默认是最小堆，所以在最大堆添加时传入负值。

import heapq


class MedianFinder:

    def __init__(self):
        self.small_heap = []  # 最大堆
        self.large_heap = []  # 最小堆

    def addNum(self, num: int) -> None:
        if len(self.small_heap) < len(self.large_heap):  # 加到small堆中
            # 先将num加到large中，再将large中的最小值弹出加入到small
            small_num = heapq.heappushpop(self.large_heap, num)
            heapq.heappush(self.small_heap, -small_num)
        else:
            # 先将num加到small中，再将small中的最小值弹出加入到large
            large_num = -heapq.heappushpop(self.small_heap, -num)
            heapq.heappush(self.large_heap, large_num)

    def findMedian(self) -> float:
        if len(self.small_heap) == len(self.large_heap):
            small = -self.small_heap[0]
            large = self.large_heap[0]
            return small + (large - small) / 2
        else:
            mid = self.large_heap[0]
            return mid

[Velliy]

"我会把答案写在留言区置顶"???

[yonggui-yan]

打卡。这波分析思路蛮好，学习了如何考虑哪些数据结构

[FRAOTIAC]

C++ 打卡，注意这个题的力扣官方题解写的有问题，大根堆要用less，小根堆用greater

class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> queLarge;
    priority_queue<int, vector<int>, greater<int>> queSmall;
    MedianFinder() {

    }
    
    void addNum(int num) {
        if (queSmall.size() >= queLarge.size()) {
            queSmall.push(num);
            queLarge.push(queSmall.top());
            queSmall.pop();
        } else {
            queLarge.push(num);
            queSmall.push(queLarge.top());
            queLarge.pop();
        }

    }
    
    double findMedian() {
        if (queSmall.size() > queLarge.size()) {
            return queSmall.top();
        } else if (queLarge.size() > queSmall.size()) {
            return queLarge.top();
        }
        return (queSmall.top() + queLarge.top()) / 2.0;
    }
};