Description
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.
- For example, for
arr = [2,3,4], the median is 3.
- For example, for
arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:
MedianFinder() initializes the MedianFinder object.void addNum(int num) adds the integer num from the data stream to the data structure.double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]
Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
Constraints:
-105 <= num <= 105- There will be at least one element in the data structure before calling
findMedian.
- At most
5 * 104 calls will be made to addNum and findMedian.
Follow up:
- If all integer numbers from the stream are in the range
[0, 100], how would you optimize your solution?
- If
99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
Solutions
Solution 1: Min Heap and Max Heap (Priority Queue)
We can use two heaps to maintain all the elements, a min heap minQ and a max heap maxQ, where the min heap minQ stores the larger half, and the max heap maxQ stores the smaller half.
When calling the addNum method, we first add the element to the max heap maxQ, then pop the top element of maxQ and add it to the min heap minQ. If at this time the size difference between minQ and maxQ is greater than 1, we pop the top element of minQ and add it to maxQ. The time complexity is O(log n).
When calling the findMedian method, if the size of minQ is equal to the size of maxQ, it means the total number of elements is even, and we can return the average value of the top elements of minQ and maxQ; otherwise, we return the top element of minQ. The time complexity is O(1).
The space complexity is O(n), where n is the number of elements.
PythonJavaC++GoTypeScriptRustJavaScriptC#Swift
class MedianFinder:
def __init__(self):
self.minq = []
self.maxq = []
def addNum(self, num: int) -> None:
heappush(self.minq, -heappushpop(self.maxq, -num))
if len(self.minq) - len(self.maxq) > 1:
heappush(self.maxq, -heappop(self.minq))
def findMedian(self) -> float:
if len(self.minq) == len(self.maxq):
return (self.minq[0] - self.maxq[0]) / 2
return self.minq[0]
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()(code-box)
class MedianFinder {
private PriorityQueue<Integer> minQ = new PriorityQueue<>();
private PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
public MedianFinder() {
}
public void addNum(int num) {
maxQ.offer(num);
minQ.offer(maxQ.poll());
if (minQ.size() - maxQ.size() > 1) {
maxQ.offer(minQ.poll());
}
}
public double findMedian() {
return minQ.size() == maxQ.size() ? (minQ.peek() + maxQ.peek()) / 2.0 : minQ.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/(code-box)
class MedianFinder {
public:
MedianFinder() {
}
void addNum(int num) {
maxQ.push(num);
minQ.push(maxQ.top());
maxQ.pop();
if (minQ.size() > maxQ.size() + 1) {
maxQ.push(minQ.top());
minQ.pop();
}
}
double findMedian() {
return minQ.size() == maxQ.size() ? (minQ.top() + maxQ.top()) / 2.0 : minQ.top();
}
private:
priority_queue<int> maxQ;
priority_queue<int, vector<int>, greater<int>> minQ;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/(code-box)
type MedianFinder struct {
minq hp
maxq hp
}
func Constructor() MedianFinder {
return MedianFinder{hp{}, hp{}}
}
func (this *MedianFinder) AddNum(num int) {
minq, maxq := &this.minq, &this.maxq
heap.Push(maxq, -num)
heap.Push(minq, -heap.Pop(maxq).(int))
if minq.Len()-maxq.Len() > 1 {
heap.Push(maxq, -heap.Pop(minq).(int))
}
}
func (this *MedianFinder) FindMedian() float64 {
minq, maxq := this.minq, this.maxq
if minq.Len() == maxq.Len() {
return float64(minq.IntSlice[0]-maxq.IntSlice[0]) / 2
}
return float64(minq.IntSlice[0])
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
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();
*/(code-box)
class MedianFinder {
#minQ = new MinPriorityQueue<number>();
#maxQ = new MaxPriorityQueue<number>();
addNum(num: number): void {
const [minQ, maxQ] = [this.#minQ, this.#maxQ];
maxQ.enqueue(num);
minQ.enqueue(maxQ.dequeue());
if (minQ.size() - maxQ.size() > 1) {
maxQ.enqueue(minQ.dequeue());
}
}
findMedian(): number {
const [minQ, maxQ] = [this.#minQ, this.#maxQ];
if (minQ.size() === maxQ.size()) {
return (minQ.front() + maxQ.front()) / 2;
}
return minQ.front();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/(code-box)
use std::cmp::Reverse;
use std::collections::BinaryHeap;
struct MedianFinder {
minQ: BinaryHeap<Reverse<i32>>,
maxQ: BinaryHeap<i32>,
}
impl MedianFinder {
fn new() -> Self {
MedianFinder {
minQ: BinaryHeap::new(),
maxQ: BinaryHeap::new(),
}
}
fn add_num(&mut self, num: i32) {
self.maxQ.push(num);
self.minQ.push(Reverse(self.maxQ.pop().unwrap()));
if self.minQ.len() > self.maxQ.len() + 1 {
self.maxQ.push(self.minQ.pop().unwrap().0);
}
}
fn find_median(&self) -> f64 {
if self.minQ.len() == self.maxQ.len() {
let min_top = self.minQ.peek().unwrap().0;
let max_top = *self.maxQ.peek().unwrap();
(min_top + max_top) as f64 / 2.0
} else {
self.minQ.peek().unwrap().0 as f64
}
}
}(code-box)
var MedianFinder = function () {
this.minQ = new MinPriorityQueue();
this.maxQ = new MaxPriorityQueue();
};
/**
* @param {number} num
* @return {void}
*/
MedianFinder.prototype.addNum = function (num) {
this.maxQ.enqueue(num);
this.minQ.enqueue(this.maxQ.dequeue());
if (this.minQ.size() - this.maxQ.size() > 1) {
this.maxQ.enqueue(this.minQ.dequeue());
}
};
/**
* @return {number}
*/
MedianFinder.prototype.findMedian = function () {
if (this.minQ.size() === this.maxQ.size()) {
return (this.minQ.front() + this.maxQ.front()) / 2;
}
return this.minQ.front();
};
/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/(code-box)
public class MedianFinder {
private PriorityQueue<int, int> minQ = new PriorityQueue<int, int>();
private PriorityQueue<int, int> maxQ = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
public MedianFinder() {
}
public void AddNum(int num) {
maxQ.Enqueue(num, num);
minQ.Enqueue(maxQ.Peek(), maxQ.Dequeue());
if (minQ.Count > maxQ.Count + 1) {
maxQ.Enqueue(minQ.Peek(), minQ.Dequeue());
}
}
public double FindMedian() {
return minQ.Count == maxQ.Count ? (minQ.Peek() + maxQ.Peek()) / 2.0 : minQ.Peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.AddNum(num);
* double param_2 = obj.FindMedian();
*/(code-box)
class MedianFinder {
private var minQ = Heap<Int>(sort: <)
private var maxQ = Heap<Int>(sort: >)
init() {
}
func addNum(_ num: Int) {
maxQ.insert(num)
minQ.insert(maxQ.remove()!)
if maxQ.count < minQ.count {
maxQ.insert(minQ.remove()!)
}
}
func findMedian() -> Double {
if maxQ.count > minQ.count {
return Double(maxQ.peek()!)
}
return (Double(maxQ.peek()!) + Double(minQ.peek()!)) / 2.0
}
}
struct Heap<T> {
var elements: [T]
let sort: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool, elements: [T] = []) {
self.sort = sort
self.elements = elements
if !elements.isEmpty {
for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
siftDown(from: i)
}
}
}
var isEmpty: Bool {
return elements.isEmpty
}
var count: Int {
return elements.count
}
func peek() -> T? {
return elements.first
}
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func remove() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let removedValue = elements.removeLast()
siftDown(from: 0)
return removedValue
}
private mutating func siftUp(from index: Int) {
var child = index
var parent = parentIndex(ofChildAt: child)
while child > 0 && sort(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = parentIndex(ofChildAt: child)
}
}
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = leftChildIndex(ofParentAt: parent)
let right = rightChildIndex(ofParentAt: parent)
var candidate = parent
if left < count && sort(elements[left], elements[candidate]) {
candidate = left
}
if right < count && sort(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent {
return
}
elements.swapAt(parent, candidate)
parent = candidate
}
}
private func parentIndex(ofChildAt index: Int) -> Int {
return (index - 1) / 2
}
private func leftChildIndex(ofParentAt index: Int) -> Int {
return 2 * index + 1
}
private func rightChildIndex(ofParentAt index: Int) -> Int {
return 2 * index + 2
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* let obj = MedianFinder()
* obj.addNum(num)
* let ret_2: Double = obj.findMedian()
*/(code-box)
