剑指 Offer 41. 数据流中的中位数

剑指offer最优解免费

本问题对应的 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()
 */

剑指offer题解