LeetCode 295. 数据流的中位数

Categories:

Tags:

题目描述
思路分析
1. 解法一：双堆维护（推荐）
相似题目

题目描述

✅ 295. 数据流的中位数

思路分析

解法一：双堆维护（推荐）

核心思路：

用一个大顶堆保存较小的一半元素，用一个小顶堆保存较大的一半元素。

保持两堆元素数目差不超过 1，且大顶堆元素都不大于小顶堆。

中位数由两堆堆顶决定：元素数相等取均值，否则取元素更多一侧的堆顶。

复杂度分析：

时间复杂度：addNum 为 O(log n)，findMedian 为 O(1)。

空间复杂度：O(n)，需要保存全部数据。

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

    public MedianFinder() {
        small = new PriorityQueue<>((a, b) -> b - a);
        large = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (small.isEmpty() || num <= small.peek()) {
            small.offer(num);
        } else {
            large.offer(num);
        }

        // 调整两堆大小，保持数量平衡
        if (small.size() > large.size() + 1) {
            large.offer(small.poll());
        } else if (large.size() > small.size()) {
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        if (small.size() == large.size()) {
            return (small.peek() + large.peek()) / 2.0;
        }
        return small.peek();
    }
}

import "container/heap"

type MinHeap []int

type MaxHeap []int

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type MedianFinder struct {
    small MaxHeap
    large MinHeap
}

func Constructor() MedianFinder {
    mf := MedianFinder{}
    heap.Init(&mf.small)
    heap.Init(&mf.large)
    return mf
}

func (mf *MedianFinder) AddNum(num int) {
    if mf.small.Len() == 0 || num <= mf.small[0] {
        heap.Push(&mf.small, num)
    } else {
        heap.Push(&mf.large, num)
    }

    // 调整两堆大小，保持数量平衡
    if mf.small.Len() > mf.large.Len()+1 {
        heap.Push(&mf.large, heap.Pop(&mf.small))
    } else if mf.large.Len() > mf.small.Len() {
        heap.Push(&mf.small, heap.Pop(&mf.large))
    }
}

func (mf *MedianFinder) FindMedian() float64 {
    if mf.small.Len() == mf.large.Len() {
        return float64(mf.small[0]+mf.large[0]) / 2.0
    }
    return float64(mf.small[0])
}

相似题目

题目	难度	考察点
239. 滑动窗口最大值	困难	堆/单调队列
480. 滑动窗口中位数	困难	双堆
剑指 Offer 41. 数据流中的中位数	困难	双堆
703. 数据流中的第 K 大元素	简单	堆
23. 合并 K 个升序链表	困难	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/62027754