AC my python solution base on binary search


  • 1
    C
    class MedianFinder:
    def __init__(self):
        self.arr = []
        self.cnt = 0
    
    def addNum(self, num):
        l = 0
        r = self.cnt
        while l < r:
            mid = l + (r-l)/2
            val = self.arr[mid]
            if val >= num:
                r = mid
            else:
                l = mid+1
        self.arr.insert(l, num)
        self.cnt += 1
    
    def findMedian(self):
        if self.cnt & 1:
            return self.arr[self.cnt/2]
        else:
            p = self.cnt/2
            v1 = self.arr[p-1]
            v2 = self.arr[ p ]
            return (v1+v2)/2.0

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.