当前位置： 面试刷题>> 数据流的中位数(经典算法150题)
### 题目描述
设计一个数据流的中位数查找器，使得任何时刻都能查询数据流中的中位数。数据流中的元素会按照非递减顺序逐个发送（即，数据流中任何时刻的元素都是已排序的，且插入操作总是在数据流的末尾进行）。
实现 `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 代码示例
```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 代码示例
```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 代码示例
```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 中实现数据流中位数查找器的方法。每种语言都根据其特性和库的支持情况进行了不同的实现。