Python beats 97% O(logn) insert and O(1) median finding 3 lines total using bisect


  • 0
    W

    Bisect lib in python helps keep a sorted array and insertion costs o(logn) because it implements a binary search on a sorted array. Finding median is just o(1) because we already know the array.

    def __init__(self):
        self.data = []
    
    def addNum(self, num):
        bisect.insort_left(self.data, num)
        
    def findMedian(self):
        return float(self.data[len(self.data)//2]) if len(self.data)%2==1 else (self.data[len(self.data)//2-1]+self.data[len(self.data)//2]) / float(2) if len(self.data) > 0 else None

Log in to reply
 

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