LeetCode 295 Find Median from Data Stream

题目链接:Find Median from Data Stream

题意:设计一个数据结构,实现下列两个操作:

  • void addNum(int num) - 将num从输入流中加入数据结构
  • double findMedian() - 返回数据结构中所有元素的中位数

可以用两个优先队列ql,qr

ql存放前(n+1)/2个数字,大数为优先级最大

qr存放后(n-1)/2个数字,小数为优先级最大

当总数为奇数时,中位数为ql的队首

当总数为偶数时,中位数为ql和qr队首的平均数

addNum()时间复杂度 \(O(log(n))\)

findMedian()时间复杂度 \(O(1)\)

 

 

 

Categories: LeetCode