剑指 Offer 41. 数据流中的中位数
本问题对应的 leetcode 原文链接：剑指 Offer 41. 数据流中的中位数
具体对应打卡问题看这里：【排序算法运用】剑指 Offer 41. 数据流中的中位数
问题描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) – 从数据流中添加一个整数到数据结构中。
- double findMedian() – 返回目前所有元素的中位数。
示例 1:
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
限制：
- 最多会对
addNum、findMedian进行50000次调用。
解题思路
视频讲解直达： 本题视频讲解
代码实现
class MedianFinder {
Queue<Integer> min, max;
/** initialize your data structure here. */
public MedianFinder() {
min = new PriorityQueue<>(); // 小根，保存较大的
max = new PriorityQueue<>((x, y) -> (y - x));// 大根
}
public void addNum(int num) {
// 如果是偶数
if(min.size() == max.size()){
min.add(num);
max.add(min.poll());
} else {
max.add(num);
min.add(max.poll());
}
}
public double findMedian() {
// 如果是偶数
if(min.size() == max.size()){
return (min.peek() + max.peek()) / 2.0;
} else {
return max.peek() * 1.0;
}
}
}
时间复杂度：1. 查找中位数 O(1)， 2. 插入元素：O(logn)
空间复杂度：O(n)
Python
import heapq
class MedianFinder(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.min = [] # 小根，保存较大的
self.max = [] # 大根
def addNum(self, num):
"""
:type num: int
:rtype: None
"""
# 如果是偶数
if len(self.min) == len(self.max):
heapq.heappush(self.min, num)
heapq.heappush(self.max, -heapq.heappop(self.min))
else:
heapq.heappush(self.max, -num)
heapq.heappush(self.min, -heapq.heappop(self.max))
def findMedian(self):
"""
:rtype: float
"""
# 如果是偶数
if len(self.min) == len(self.max):
return (self.min[0] + (-self.max[0])) / 2.0
else:
return -self.max[0] * 1.0
C++
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
// 如果是偶数
if(min_heap.size() == max_heap.size()){
min_heap.push(num);
max_heap.push(min_heap.top());
min_heap.pop();
} else {
max_heap.push(num);
min_heap.push(max_heap.top());
max_heap.pop();
}
}
double findMedian() {
// 如果是偶数
if(min_heap.size() == max_heap.size()){
return (min_heap.top() + max_heap.top()) / 2.0;
} else {
return max_heap.top();
}
}
private:
priority_queue<int> min_heap; // 小根，保存较大的
priority_queue<int, vector<int>, greater<int>> max_heap; // 大根
};
Go
import "container/heap"
type MinHeap []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[0 : n-1]
return x
}
func (h *MinHeap) Peek() int {
return (*h)[0]
}
type MaxHeap struct {
MinHeap
}
func (h MaxHeap) Less(i, j int) bool {
return h.MinHeap[i] > h.MinHeap[j]
}
type MedianFinder struct {
min *MinHeap // 小根，保存较大的
max *MaxHeap // 大根
}
/** initialize your data structure here. */
func Constructor() MedianFinder {
return MedianFinder{
min: &MinHeap{},
max: &MaxHeap{},
}
}
func (this *MedianFinder) AddNum(num int) {
// 如果是偶数
if this.min.Len() == this.max.Len() {
heap.Push(this.min, num)
heap.Push(this.max, heap.Pop(this.min))
} else {
heap.Push(this.max, num)
heap.Push(this.min, heap.Pop(this.max))
}
}
func (this *MedianFinder) FindMedian() float64 {
// 如果是偶数
if this.min.Len() == this.max.Len() {
return float64(this.min.Peek() + this.max.Peek()) / 2.0
} else {
return float64(this.max.Peek())
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* obj := Constructor();
* obj.AddNum(num);
* param_2 := obj.FindMedian();
*/
JS
/**
* initialize your data structure here.
*/
var MedianFinder = function() {
this.min = [];
this.max = [];
};
/**
* @param {number} num
* @return {void}
*/
MedianFinder.prototype.addNum = function(num) {
// 如果是偶数
if (this.min.length === this.max.length) {
this.min.push(num);
this.max.push(this.min.shift());
} else {
this.max.push(num);
this.min.push(this.max.shift());
}
};
/**
* @return {number}
*/
MedianFinder.prototype.findMedian = function() {
// 如果是偶数
if (this.min.length === this.max.length) {
return (this.min[0] + this.max[0]) / 2.0;
} else {
return this.max[0] * 1.0;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/