题目描述

设计一个数据流的中位数查找器，使得任何时刻都能查询数据流中的中位数。数据流中的元素会按照非递减顺序逐个发送（即，数据流中任何时刻的元素都是已排序的，且插入操作总是在数据流的末尾进行）。

实现 MedianFinder 类：

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将一个整数 num 添加到数据流的末尾。
• double findMedian() 返回数据流中的中位数。如果数据流中元素的数量是奇数，则返回中间元素；如果是偶数，则返回中间两个元素的平均值。

示例

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);
medianFinder.addNum(2);
medianFinder.findMedian(); // 返回 1.5，因为数据流中有两个元素 [1, 2]，中位数是 (1 + 2) / 2 = 1.5
medianFinder.addNum(3);
medianFinder.findMedian(); // 返回 2.0，因为数据流中有三个元素 [1, 2, 3]，中位数是 2

PHP 代码示例

class MedianFinder {
    private $maxHeap; // 存储较小的一半元素
    private $minHeap; // 存储较大的一半元素

    function __construct() {
        $this->maxHeap = new SplMaxHeap(); // PHP SplMaxHeap 实现最大堆
        $this->minHeap = new SplMinHeap(); // PHP SplMinHeap 实现最小堆
    }

    function addNum($num) {
        if ($this->maxHeap->isEmpty() || $num <= $this->maxHeap->top()) {
            $this->maxHeap->insert($num);
        } else {
            $this->minHeap->insert($num);
        }

        // 保持两个堆的平衡
        if ($this->maxHeap->count() > $this->minHeap->count() + 1) {
            $this->minHeap->insert($this->maxHeap->extract());
        } elseif ($this->minHeap->count() > $this->maxHeap->count()) {
            $this->maxHeap->insert($this->minHeap->extract());
        }
    }

    function findMedian() {
        if ($this->maxHeap->count() > $this->minHeap->count()) {
            return $this->maxHeap->top();
        } else {
            return ($this->maxHeap->top() + $this->minHeap->top()) / 2.0;
        }
    }
}

注意： PHP 标准库中没有直接支持优先队列（堆）的类，这里使用 SplMaxHeap 和 SplMinHeap 作为示例，实际使用中可能需要自定义实现或使用第三方库。

Python 代码示例

import heapq

class MedianFinder:
    def __init__(self):
        self.maxHeap = []  # 较小的一半元素，使用最小堆
        self.minHeap = []  # 较大的一半元素，使用最大堆（Python heapq 是最小堆，所以存储时取反）

    def addNum(self, num):
        heapq.heappush(self.maxHeap, -heapq.heappushpop(self.minHeap, -num) if self.maxHeap and num > -self.maxHeap[0] else num)
        if len(self.maxHeap) > len(self.minHeap) + 1:
            heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))
        elif len(self.minHeap) > len(self.maxHeap):
            heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))

    def findMedian(self):
        if len(self.maxHeap) > len(self.minHeap):
            return -self.maxHeap[0]
        else:
            return (-self.maxHeap[0] + self.minHeap[0]) / 2.0

JavaScript 代码示例

class MedianFinder {
    constructor() {
        this.maxHeap = []; // 较小的一半元素，使用最大堆（JavaScript 需要自定义实现）
        this.minHeap = []; // 较大的一半元素，使用最小堆（JavaScript 数组模拟）

        this.maxHeapify = (arr, i, heapSize) => {
            let largest = i;
            let left = 2 * i + 1;
            let right = 2 * i + 2;

            if (left < heapSize && arr[left] > arr[largest]) {
                largest = left;
            }
            if (right < heapSize && arr[right] > arr[largest]) {
                largest = right;
            }
            if (largest !== i) {
                [arr[i], arr[largest]] = [arr[largest], arr[i]];
                this.maxHeapify(arr, largest, heapSize);
            }
        };

        this.minHeapify = (arr, i, heapSize) => {
            let smallest = i;
            let left = 2 * i + 1;
            let right = 2 * i + 2;

            if (left < heapSize && arr[left] < arr[smallest]) {
                smallest = left;
            }
            if (right < heapSize && arr[right] < arr[smallest]) {
                smallest = right;
            }
            if (smallest !== i) {
                [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
                this.minHeapify(arr, smallest, heapSize);
            }
        };

        this.shiftUpMaxHeap = (arr, index) => {
            while (index > 0 && arr[Math.floor((index - 1) / 2)] < arr[index]) {
                [arr[index], arr[Math.floor((index - 1) / 2)]] = [arr[Math.floor((index - 1) / 2)], arr[index]];
                index = Math.floor((index - 1) / 2);
            }
        };

        this.shiftUpMinHeap = (arr, index) => {
            while (index > 0 && -arr[Math.floor((index - 1) / 2)] > -arr[index]) {
                [arr[index], arr[Math.floor((index - 1) / 2)]] = [arr[Math.floor((index - 1) / 2)], arr[index]];
                index = Math.floor((index - 1) / 2);
            }
        };
    }

    addNum(num) {
        if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) {
            this.maxHeap.push(num);
            this.shiftUpMaxHeap(this.maxHeap, this.maxHeap.length - 1);
        } else {
            this.minHeap.push(-num);
            this.shiftUpMinHeap(this.minHeap, this.minHeap.length - 1);
        }

        // 保持两个堆的平衡
        if (this.maxHeap.length > this.minHeap.length + 1) {
            this.minHeap.push(-this.maxHeap.shift());
            this.minHeapify(this.minHeap, 0, this.minHeap.length);
        } elseif (this.minHeap.length > this.maxHeap.length) {
            this.maxHeap.push(-this.minHeap.shift());
            this.maxHeapify(this.maxHeap, 0, this.maxHeap.length);
        }
    }

    findMedian() {
        if (this.maxHeap.length > this.minHeap.length) {
            return -this.maxHeap[0];
        } else {
            return (-this.maxHeap[0] + this.minHeap[0]) / 2.0;
        }
    }
}

以上代码示例提供了在 PHP、Python 和 JavaScript 中实现数据流中位数查找器的方法。每种语言都根据其特性和库的支持情况进行了不同的实现。