classMedianFinder:def__init__(self):""" initialize your data structure here. """self.q1=[]self.q2=[]defaddNum(self,num:int)->None:iflen(self.q1)>len(self.q2):heappush(self.q2,-heappushpop(self.q1,num))else:heappush(self.q1,-heappushpop(self.q2,-num))deffindMedian(self)->float:iflen(self.q1)>len(self.q2):returnself.q1[0]return(self.q1[0]-self.q2[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<>((a,b)->b-a);/** initialize your data structure here. */publicMedianFinder(){}publicvoidaddNum(intnum){if(q1.size()>q2.size()){q1.offer(num);q2.offer(q1.poll());}else{q2.offer(num);q1.offer(q2.poll());}}publicdoublefindMedian(){if(q1.size()>q2.size()){returnq1.peek();}return(q1.peek()+q2.peek())/2.0;}}/** * 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){if(q1.size()>q2.size()){q1.push(num);q2.push(q1.top());q1.pop();}else{q2.push(num);q1.push(q2.top());q2.pop();}}doublefindMedian(){if(q1.size()>q2.size()){returnq1.top();}return(q1.top()+q2.top())/2.0;}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{q1,q2hp}/** initialize your data structure here. */funcConstructor()MedianFinder{returnMedianFinder{hp{},hp{}}}func(this*MedianFinder)AddNum(numint){ifthis.q1.Len()>this.q2.Len(){heap.Push(&this.q1,num)heap.Push(&this.q2,-heap.Pop(&this.q1).(int))}else{heap.Push(&this.q2,-num)heap.Push(&this.q1,-heap.Pop(&this.q2).(int))}}func(this*MedianFinder)FindMedian()float64{ifthis.q1.Len()>this.q2.Len(){returnfloat64(this.q1.IntSlice[0])}returnfloat64(this.q1.IntSlice[0]-this.q2.IntSlice[0])/2.0}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}/** * Your MedianFinder object will be instantiated and called as such: * obj := Constructor(); * obj.AddNum(num); * param_2 := obj.FindMedian(); */
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(); */
方法二
1 2 3 4 5 6 7 8 9101112131415161718192021222324
fromsortedcontainersimportSortedListclassMedianFinder:def__init__(self):""" initialize your data structure here. """self.sl=SortedList()defaddNum(self,num:int)->None:self.sl.add(num)deffindMedian(self)->float:n=len(self.sl)ifn&1:returnself.sl[n//2]return(self.sl[(n-1)//2]+self.sl[n//2])/2# Your MedianFinder object will be instantiated and called as such:# obj = MedianFinder()# obj.addNum(num)# param_2 = obj.findMedian()