class MovingAverage(object): def __init__(self, size): self.vect, self.sums, self.idx, self.size =  * size, 0, 0, size def next(self, val): self.idx += 1 self.sums -= self.vect[self.idx % self.size] self.vect[self.idx % self.size] = val self.sums += val return self.sums / float(min(self.idx, self.size))
My solution requires real
O(1) time for
next() operation as it is not needed to compute the sum every time. We just subtract the element that is exiting from the sliding window, and we're done. We need also to substitute that element with the new one.
@agave Can you explain the brain working on how you reached this solution?
The circular array idea is very nice, thank you! I just have a minor suggestion, not sure if you like it.
You can initiate your self.sum to be float (0.0), so you wouldn't need to convert the integer to float explicitly. I also did some local testing, without explicitly convert int to float the speed of adding two numbers is two times faster.
a = 1 a += float(2) # VS a = 1.0 a += 2
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.