2023-8-31

8-31

数组

题号剑指 Offer 41. 数据流中的中位数

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

• void addNum(int num) - 从数据流中添加一个整数到数据结构中。
• double findMedian() - 返回目前所有元素的中位数。

思路 中位数的计算方法：首先对数组执行排序，然后返回中间元素即可

针对这个思路，我们可以把数据保存在一个列表里，添加元素的时候也保证数组是有序的。（借助堆可以优化时间复杂度）

细节直接看大佬的题解就行了https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solutions/227309/mian-shi-ti-41-shu-ju-liu-zhong-de-zhong-wei-shu-y/

解法一 （面试别用

class MedianFinder {
    private nums = []

    constructor() {
    }

    addNum(num: number): void {
        this.nums.push(num)
    }

    findMedian(): number {
        this.nums.sort((a,b)=>a-b)
        if(this.nums.length%2===0){
            return (this.nums[Math.floor(this.nums.length/2)]+ this.nums[Math.floor(this.nums.length/2)-1])/2
        }else{
            return this.nums[Math.floor(this.nums.length/2)]
        }
    }
}

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

解法二 堆解法

import { Heap } from 'heap';

class MedianFinder {
    private A: Heap<number>;  // 小顶堆，保存较大的一半
    private B: Heap<number>;  // 大顶堆，保存较小的一半

    constructor() {
        this.A = new Heap<number>();  // 使用 heap 库创建小顶堆，默认为升序
        this.B = new Heap<number>({ comparisonFunc: (x, y) => y - x });  // 创建大顶堆，传入降序比较函数
    }

    addNum(num: number): void {
        if (this.A.size() !== this.B.size()) {
            this.A.push(num);
            this.B.push(this.A.pop());
        } else {
            this.B.push(num);
            this.A.push(this.B.pop());
        }
    }

    findMedian(): number {
        return this.A.size() !== this.B.size()
            ? this.A.peek()
            : (this.A.peek() + this.B.peek()) / 2.0;
    }
}

// 示例使用
const medianFinder = new MedianFinder();
medianFinder.addNum(1);
medianFinder.addNum(2);
console.log(medianFinder.findMedian());  // 输出: 1.5
medianFinder.addNum(3);
console.log(medianFinder.findMedian());  // 输出: 2