| comments | difficulty | edit_url |
|---|---|---|
true |
Hard |
Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example,
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
- void addNum(int num) - Add a integer number from the data stream to the data structure.
- double findMedian() - Return the median of all elements so far.
Example:
addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2
We can use two heaps to maintain all the elements, a min heap
When calling the addNum method, we first add the element to the max heap
When calling the findMedian method, if the size of
The space complexity is
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()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();
*/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();
*/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();
*/class MedianFinder {
#minQ = new MinPriorityQueue();
#maxQ = new MaxPriorityQueue();
addNum(num: number): void {
const [minQ, maxQ] = [this.#minQ, this.#maxQ];
maxQ.enqueue(num);
minQ.enqueue(maxQ.dequeue().element);
if (minQ.size() - maxQ.size() > 1) {
maxQ.enqueue(minQ.dequeue().element);
}
}
findMedian(): number {
const [minQ, maxQ] = [this.#minQ, this.#maxQ];
if (minQ.size() === maxQ.size()) {
return (minQ.front().element + maxQ.front().element) / 2;
}
return minQ.front().element;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/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
}
}
}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().element);
if (this.minQ.size() - this.maxQ.size() > 1) {
this.maxQ.enqueue(this.minQ.dequeue().element);
}
};
/**
* @return {number}
*/
MedianFinder.prototype.findMedian = function () {
if (this.minQ.size() === this.maxQ.size()) {
return (this.minQ.front().element + this.maxQ.front().element) / 2;
}
return this.minQ.front().element;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/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();
*/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()
*/