面试题 17.20. 连续中值
随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
示例：
addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2
原站题解
golang 解法, 执行用时: 88 ms, 内存消耗: 12.4 MB, 提交时间: 2022-11-30 23:36:45
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 解法, 执行用时: 300 ms, 内存消耗: 26.8 MB, 提交时间: 2022-11-30 23:36:16
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()
java 解法, 执行用时: 73 ms, 内存消耗: 52.6 MB, 提交时间: 2022-11-30 23:35:58
class MedianFinder {
TreeMap<Integer, Integer> nums;
int n;
int[] left;
int[] right;
public MedianFinder() {
nums = new TreeMap<Integer, Integer>();
n = 0;
left = new int[2];
right = new int[2];
}
public void addNum(int num) {
nums.put(num, nums.getOrDefault(num, 0) + 1);
if (n == 0) {
left[0] = right[0] = num;
left[1] = right[1] = 1;
} else if ((n & 1) != 0) {
if (num < left[0]) {
decrease(left);
} else {
increase(right);
}
} else {
if (num > left[0] && num < right[0]) {
increase(left);
decrease(right);
} else if (num >= right[0]) {
increase(left);
} else {
decrease(right);
System.arraycopy(right, 0, left, 0, 2);
}
}
n++;
}
public double findMedian() {
return (left[0] + right[0]) / 2.0;
}
private void increase(int[] iterator) {
iterator[1]++;
if (iterator[1] > nums.get(iterator[0])) {
iterator[0] = nums.ceilingKey(iterator[0] + 1);
iterator[1] = 1;
}
}
private void decrease(int[] iterator) {
iterator[1]--;
if (iterator[1] == 0) {
iterator[0] = nums.floorKey(iterator[0] - 1);
iterator[1] = nums.get(iterator[0]);
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
java 解法, 执行用时: 61 ms, 内存消耗: 52.7 MB, 提交时间: 2022-11-30 23:35:32
class MedianFinder {
PriorityQueue<Integer> queMin;
PriorityQueue<Integer> queMax;
public MedianFinder() {
queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
}
public void addNum(int num) {
if (queMin.isEmpty() || num <= queMin.peek()) {
queMin.offer(num);
if (queMax.size() + 1 < queMin.size()) {
queMax.offer(queMin.poll());
}
} else {
queMax.offer(num);
if (queMax.size() > queMin.size()) {
queMin.offer(queMax.poll());
}
}
}
public double findMedian() {
if (queMin.size() > queMax.size()) {
return queMin.peek();
}
return (queMin.peek() + queMax.peek()) / 2.0;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
golang 解法, 执行用时: 84 ms, 内存消耗: 13.8 MB, 提交时间: 2022-11-30 23:35:07
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();
*/
python3 解法, 执行用时: 164 ms, 内存消耗: 26.1 MB, 提交时间: 2022-11-30 23:34:44
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()