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 m.next(10) = (1 + 10) / 2 m.next(3) = (1 + 10 + 3) / 3 m.next(5) = (10 + 3 + 5) / 3 |
Use (and keep updating) the running total of the List to help calculate the moving average in O(1) time.
class MovingAverage { List<Integer> nums; double sum; int size; /** Initialize your data structure here. */ public MovingAverage(int size) { this.nums = new ArrayList<Integer>(); this.sum = 0; this.size = size; } public double next(int val) { nums.add(val); if ( nums.size() <= this.size ) { this.sum += val; return this.sum/nums.size(); } int num = nums.remove(0); this.sum = this.sum - num + val; return this.sum/nums.size(); } } /** * Your MovingAverage object will be instantiated and called as such: * MovingAverage obj = new MovingAverage(size); * double param_1 = obj.next(val); */ |