当前位置：首页 > article >正文

LeetCode hot100-76

article 2024/12/22 10:06:14

https://leetcode.cn/problems/find-median-from-data-stream/description/?envType=study-plan-v2&envId=top-100-liked

295. 数据流的中位数
已解答
困难
相关标签
相关企业
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。

void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

这道题用List直接算中位数会超时

class MedianFinder {

    ArrayList<Integer> list;
    public MedianFinder() {
        list = new ArrayList<>();
    }
    
    public void addNum(int num) {
        list.add(num);
        
    }
    
    public double findMedian() {
        // 1. 排序列表
        Collections.sort(list);

        // 2. 获取列表的大小
        int size = list.size();

        // 3. 根据列表大小判断是奇数还是偶数
        if (size % 2 == 1) {
            // 如果是奇数，返回中间的元素
            return list.get(size / 2);
        } else {
            // 如果是偶数，返回中间两个元素的平均值
            int mid1 = list.get(size / 2 - 1);
            int mid2 = list.get(size / 2);
            return (mid1 + mid2) / 2.0;  // 注意：返回值是 double 类型
        }
        
    }
}

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

思路就是用两个堆。小顶堆保存最大的一半数字。大顶堆保存最小的一半数字。然后求中位数就只需要关注两个堆顶就行。如何做到，看代码吧。主要就是顺序地一个堆进一个数字，就保证了两个堆一人一半数字。小顶堆为最大的一半就是将数字从大顶堆过一遍再把堆顶给小顶堆就可以做到了。

class MedianFinder {
    Queue<Integer> A, B;
    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() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}