classMedianFinder:def__init__(self):""" initialize your data structure here. """self.h1=[]self.h2=[]defaddNum(self,num:int)->None:heappush(self.h1,num)heappush(self.h2,-heappop(self.h1))iflen(self.h2)-len(self.h1)>1:heappush(self.h1,-heappop(self.h2))deffindMedian(self)->float:iflen(self.h2)>len(self.h1):return-self.h2[0]return(self.h1[0]-self.h2[0])/2# Your MedianFinder object will be instantiated and called as such:# obj = MedianFinder()# obj.addNum(num)# param_2 = obj.findMedian()
classMedianFinder{privatePriorityQueue<Integer>q1=newPriorityQueue<>();privatePriorityQueue<Integer>q2=newPriorityQueue<>(Collections.reverseOrder());/** initialize your data structure here. */publicMedianFinder(){}publicvoidaddNum(intnum){q1.offer(num);q2.offer(q1.poll());if(q2.size()-q1.size()>1){q1.offer(q2.poll());}}publicdoublefindMedian(){if(q2.size()>q1.size()){returnq2.peek();}return(q1.peek()+q2.peek())*1.0/2;}}/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */
classMedianFinder{public:/** initialize your data structure here. */MedianFinder(){}voidaddNum(intnum){q1.push(num);q2.push(q1.top());q1.pop();if(q2.size()-q1.size()>1){q1.push(q2.top());q2.pop();}}doublefindMedian(){if(q2.size()>q1.size()){returnq2.top();}return(double)(q1.top()+q2.top())/2;}private:priority_queue<int,vector<int>,greater<int>>q1;priority_queue<int>q2;};/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
typeMedianFinderstruct{q1hpq2hp}/** initialize your data structure here. */funcConstructor()MedianFinder{returnMedianFinder{hp{},hp{}}}func(this*MedianFinder)AddNum(numint){heap.Push(&this.q1,num)heap.Push(&this.q2,-heap.Pop(&this.q1).(int))ifthis.q2.Len()-this.q1.Len()>1{heap.Push(&this.q1,-heap.Pop(&this.q2).(int))}}func(this*MedianFinder)FindMedian()float64{ifthis.q2.Len()>this.q1.Len(){return-float64(this.q2.IntSlice[0])}returnfloat64(this.q1.IntSlice[0]-this.q2.IntSlice[0])/2.0}/** * Your MedianFinder object will be instantiated and called as such: * obj := Constructor(); * obj.AddNum(num); * param_2 := obj.FindMedian(); */typehpstruct{sort.IntSlice}func(hhp)Less(i,jint)bool{returnh.IntSlice[i]<h.IntSlice[j]}func(h*hp)Push(vany){h.IntSlice=append(h.IntSlice,v.(int))}func(h*hp)Pop()any{a:=h.IntSlicev:=a[len(a)-1]h.IntSlice=a[:len(a)-1]returnv}
classMedianFinder{privatenums:number[];constructor(){this.nums=[];}addNum(num:number):void{const{nums}=this;letl=0;letr=nums.length;while(l<r){constmid=(l+r)>>>1;if(nums[mid]<num){l=mid+1;}else{r=mid;}}nums.splice(l,0,num);}findMedian():number{const{nums}=this;constn=nums.length;if((n&1)===1){returnnums[n>>1];}return(nums[n>>1]+nums[(n>>1)-1])/2;}}/** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */
structMedianFinder{nums:Vec<i32>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implMedianFinder{/** initialize your data structure here. */fnnew()->Self{Self{nums:Vec::new()}}fnadd_num(&mutself,num:i32){letmutl=0;letmutr=self.nums.len();whilel<r{letmid=(l+r)>>1;ifself.nums[mid]<num{l=mid+1;}else{r=mid;}}self.nums.insert(l,num);}fnfind_median(&self)->f64{letn=self.nums.len();if(n&1)==1{returnf64::from(self.nums[n>>1]);}f64::from(self.nums[n>>1]+self.nums[(n>>1)-1])/2.0}}/** * Your MedianFinder object will be instantiated and called as such: * let obj = MedianFinder::new(); * obj.add_num(num); * let ret_2: f64 = obj.find_median(); */
publicclassMedianFinder{privateList<int>nums;privateintcurIndex;/** initialize your data structure here. */publicMedianFinder(){nums=newList<int>();}privateintFindIndex(intval){intleft=0;intright=nums.Count-1;while(left<=right){intmid=left+(right-left)/2;if(val>nums[mid]){left=mid+1;}else{right=mid-1;}}returnleft;}publicvoidAddNum(intnum){if(nums.Count==0){nums.Add(num);curIndex=0;}else{curIndex=FindIndex(num);if(curIndex==nums.Count){nums.Add(num);}else{nums.Insert(curIndex,num);}}}publicdoubleFindMedian(){if(nums.Count%2==1){return(double)nums[nums.Count/2];}else{if(nums.Count==0){return0;}else{return(double)(nums[nums.Count/2-1]+nums[nums.Count/2])/2;}}}}/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.AddNum(num); * double param_2 = obj.FindMedian(); */