11public class MedianFinder {
2+ private PriorityQueue < int , int > leftHeap = new ( Comparer < int > . Create ( ( a , b ) => b - a ) ) ;
3+ private PriorityQueue < int , int > rightHeap = new ( ) ;
24
3- List < int > Nums ;
45public MedianFinder ( ) {
56
6- Nums = new List < int > ( ) ;
77}
88
9+ // T: log(n)
910public void AddNum ( int num ) {
10- int index = Nums . BinarySearch ( num ) ;
11- if ( index < 0 )
12- {
13- index = ~ index ;
14- }
15- Nums . Insert ( index , num ) ;
11+ if ( leftHeap . Count == 0 || num > leftHeap . Peek ( ) )
12+ rightHeap . Enqueue ( num , num ) ;
13+ else
14+ leftHeap . Enqueue ( num , num ) ;
15+
16+ Balance ( ) ;
17+ }
18+
19+ private void Balance ( ) {
20+ var ( big , small ) = leftHeap . Count > rightHeap . Count
21+ ? ( leftHeap , rightHeap )
22+ : ( rightHeap , leftHeap ) ;
23+
24+ while ( big . Count - small . Count > 1 ) {
25+ var value = big . Dequeue ( ) ;
26+ small . Enqueue ( value , value ) ;
27+ }
1628}
1729
30+ // T: O(1)
1831public double FindMedian ( ) {
19- int count = Nums . Count ;
20- return count % 2 == 0 ? ( double ) ( ( Nums [ count / 2 - 1 ] + Nums [ count / 2 ] ) * 0.5 ) : Nums [ count / 2 ] ;
32+ if ( leftHeap . Count == rightHeap . Count )
33+ return ( leftHeap . Peek ( ) + rightHeap . Peek ( ) ) / 2.0 ;
34+
35+ return leftHeap . Count > rightHeap . Count
36+ ? leftHeap . Peek ( )
37+ : rightHeap . Peek ( ) ;
2138}
2239}
2340
@@ -26,59 +43,4 @@ public double FindMedian() {
2643 * MedianFinder obj = new MedianFinder();
2744 * obj.AddNum(num);
2845 * double param_2 = obj.FindMedian();
29-
30- // ***IMP : Not passing for few test cases
31- class MedianFinder
32- {
33-
34- private PriorityQueue<int, int> smallHeap; //small elements - maxHeap
35- private PriorityQueue<int, int> largeHeap; //large elements - minHeap
36-
37- public MedianFinder()
38- {
39- smallHeap = new PriorityQueue<int, int>();
40- largeHeap = new PriorityQueue<int, int>();
41- }
42-
43- public void addNum(int num)
44- {
45- smallHeap.Enqueue(num, num);
46- if (
47- smallHeap.Count - largeHeap.Count > 1 ||
48- !(largeHeap.Count <= 0) &&
49- smallHeap.Peek() > largeHeap.Peek()
50- )
51- {
52- if (smallHeap.Count > 0)
53- {
54- int ele = smallHeap.Dequeue();
55- largeHeap.Enqueue(ele, ele);
56- }
57- }
58- if (largeHeap.Count - smallHeap.Count > 1)
59- {
60- if (largeHeap.Count > 0)
61- {
62- int ele = largeHeap.Dequeue();
63- smallHeap.Enqueue(ele, ele);
64- }
65- }
66- }
67-
68- public double findMedian()
69- {
70- if (smallHeap.Count == largeHeap.Count)
71- {
72- return (double)(largeHeap.Peek() + smallHeap.Peek()) / 2;
73- }
74- else if (smallHeap.Count > largeHeap.Count)
75- {
76- return (double)smallHeap.Peek();
77- }
78- else
79- {
80- return (double)largeHeap.Peek();
81- }
82- }
83- }
8446 */