Efficient python solution using deque


  • 0
    S

    I see another 4-line solution here but I don't think it is efficient. it has to do a sum (which is O(n)) each time calling next.
    instead, in my solution I keep a sum variable and every time I just need to do a O(1) update to it.

    class MovingAverage(object):

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.maxsize = size
        self.sum = 0
        self.window = collections.deque()
    
    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        self.window.append(val)
        if len(self.window) < self.maxsize:
            self.sum += val
        else:
            self.sum += val - self.window.popleft()
            
        return self.sum/self.maxsize
    

    Your MovingAverage object will be instantiated and called as such:

    obj = MovingAverage(size)

    param_1 = obj.next(val)


  • 0
    G

    Thank you for sharing the code.
    I was just wondering, when you return self.sum/self.maxsize, should it be self.sum/(len(self.window))?
    Also how do you deal with the float which the questions asked for instead of int?


Log in to reply
 

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