剑指 Offer 41. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
示例 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 次调用。注意：本题与主站 295 题相同：https://leetcode.cn/problems/find-median-from-data-stream/
原站题解
golang 解法, 执行用时: 80 ms, 内存消耗: 14.6 MB, 提交时间: 2022-11-14 11:30:52
type MedianFinder struct {
queMin, queMax hp
}
func Constructor() MedianFinder {
return MedianFinder{}
}
func (mf *MedianFinder) AddNum(num int) {
minQ, maxQ := &mf.queMin, &mf.queMax
if minQ.Len() == 0 || num <= -minQ.IntSlice[0] {
heap.Push(minQ, -num)
if maxQ.Len()+1 < minQ.Len() {
heap.Push(maxQ, -heap.Pop(minQ).(int))
}
} else {
heap.Push(maxQ, num)
if maxQ.Len() > minQ.Len() {
heap.Push(minQ, -heap.Pop(maxQ).(int))
}
}
}
func (mf *MedianFinder) FindMedian() float64 {
minQ, maxQ := mf.queMin, mf.queMax
if minQ.Len() > maxQ.Len() {
return float64(-minQ.IntSlice[0])
}
return float64(maxQ.IntSlice[0]-minQ.IntSlice[0]) / 2
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
/**
* Your MedianFinder object will be instantiated and called as such:
* obj := Constructor();
* obj.AddNum(num);
* param_2 := obj.FindMedian();
*/
golang 解法, 执行用时: 84 ms, 内存消耗: 12.8 MB, 提交时间: 2022-11-14 11:30:13
type MedianFinder struct {
nums *redblacktree.Tree
total int
left, right iterator
}
func Constructor() MedianFinder {
return MedianFinder{nums: redblacktree.NewWithIntComparator()}
}
func (mf *MedianFinder) AddNum(num int) {
if count, has := mf.nums.Get(num); has {
mf.nums.Put(num, count.(int)+1)
} else {
mf.nums.Put(num, 1)
}
if mf.total == 0 {
it := mf.nums.Iterator()
it.Next()
mf.left = iterator{it, 1}
mf.right = mf.left
} else if mf.total%2 == 1 {
if num < mf.left.Key().(int) {
mf.left.prev()
} else {
mf.right.next()
}
} else {
if mf.left.Key().(int) < num && num < mf.right.Key().(int) {
mf.left.next()
mf.right.prev()
} else if num >= mf.right.Key().(int) {
mf.left.next()
} else {
mf.right.prev()
mf.left = mf.right
}
}
mf.total++
}
func (mf *MedianFinder) FindMedian() float64 {
return float64(mf.left.Key().(int)+mf.right.Key().(int)) / 2
}
type iterator struct {
redblacktree.Iterator
count int
}
func (it *iterator) prev() {
if it.count > 1 {
it.count--
} else {
it.Prev()
it.count = it.Value().(int)
}
}
func (it *iterator) next() {
if it.count < it.Value().(int) {
it.count++
} else {
it.Next()
it.count = 1
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* obj := Constructor();
* obj.AddNum(num);
* param_2 := obj.FindMedian();
*/
python3 解法, 执行用时: 284 ms, 内存消耗: 26.6 MB, 提交时间: 2022-11-14 11:29:38
from sortedcontainers import SortedList
class MedianFinder:
def __init__(self):
self.nums = SortedList()
self.left = self.right = None
self.left_value = self.right_value = None
def addNum(self, num: int) -> None:
nums_ = self.nums
n = len(nums_)
nums_.add(num)
if n == 0:
self.left = self.right = 0
else:
# 模拟双指针，当 num 小于 self.left 或 self.right 指向的元素时，num 的加入会导致对应指针向右移动一个位置
if num < self.left_value:
self.left += 1
if num < self.right_value:
self.right += 1
if n & 1:
if num < self.left_value:
self.left -= 1
else:
self.right += 1
else:
if self.left_value < num < self.right_value:
self.left += 1
self.right -= 1
elif num >= self.right_value:
self.left += 1
else:
self.right -= 1
self.left = self.right
self.left_value = nums_[self.left]
self.right_value = nums_[self.right]
def findMedian(self) -> float:
return (self.left_value + self.right_value) / 2
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
python3 解法, 执行用时: 168 ms, 内存消耗: 26 MB, 提交时间: 2022-11-14 11:29:13
class MedianFinder:
def __init__(self):
self.queMin = list()
self.queMax = list()
def addNum(self, num: int) -> None:
queMin_ = self.queMin
queMax_ = self.queMax
if not queMin_ or num <= -queMin_[0]:
heapq.heappush(queMin_, -num)
if len(queMax_) + 1 < len(queMin_):
heapq.heappush(queMax_, -heapq.heappop(queMin_))
else:
heapq.heappush(queMax_, num)
if len(queMax_) > len(queMin_):
heapq.heappush(queMin_, -heapq.heappop(queMax_))
def findMedian(self) -> float:
queMin_ = self.queMin
queMax_ = self.queMax
if len(queMin_) > len(queMax_):
return -queMin_[0]
return (-queMin_[0] + queMax_[0]) / 2
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()