-
Notifications
You must be signed in to change notification settings - Fork 119
/
Copy pathFind Median from Data Stream.js
49 lines (44 loc) · 1.12 KB
/
Find Median from Data Stream.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Runtime: 963 ms (Top 55.56%) | Memory: 101.7 MB (Top 5.32%)
var MedianFinder = function() {
this.left = new MaxPriorityQueue();
this.right = new MinPriorityQueue();
};
/**
* @param {number} num
* @return {void}
*/
MedianFinder.prototype.addNum = function(num) {
let { right, left } = this
if (right.size() > 0 && num > right.front().element) {
right.enqueue(num)
} else {
left.enqueue(num)
}
if (Math.abs(left.size() - right.size()) == 2) {
if (left.size() > right.size()) {
right.enqueue(left.dequeue().element)
} else {
left.enqueue(right.dequeue().element)
}
}
};
/**
* @return {number}
*/
MedianFinder.prototype.findMedian = function() {
let { left, right } = this
if (left.size() > right.size()) {
return left.front().element
} else if(right.size() > left.size()) {
return right.front().element
} else{
// get the sum of all
return (left.front().element + right.front().element) / 2
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/