- Moving Average from Data Stream
LC: 346
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Example
MovingAverage m = new MovingAverage(3);
m.next(1) = 1 // return 1.00000
m.next(10) = (1 + 10) / 2 // return 5.50000
m.next(3) = (1 + 10 + 3) / 3 // return 4.66667
m.next(5) = (10 + 3 + 5) / 3 // return 6.00000
class MovingAverage:
"""
@param: size: An integer
"""
def __init__(self, size):
# do intialization if necessary
self.total = 0
self.cap = size
self.nums = []
"""
@param: val: An integer
@return:
"""
def next(self, val):
# write your code here
if len(self.nums) == self.cap:
self.total -= self.nums.pop(0)
self.nums.append(val)
self.total += val
return self.total / len(self.nums)
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param = obj.next(val)
- Time:
O(1) for both - Space:
O(size) for the object
Notes:
One key point here is to use a queue to keep track of all nums in window.
