Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
For 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
Solution:
Use a Queue serve as a sliding window, and also maintain the current sum inside of the window.
Code (Java):
public class MovingAverage { Queue<Integer> queue; int n; int sum; /** Initialize your data structure here. */ public MovingAverage(int size) { queue = new LinkedList<>(); n = size; sum = 0; } public double next(int val) { queue.offer(val); double result = 0; sum += val; if (queue.size() <= n) { result = (double) sum / queue.size(); } else { int remove = queue.poll(); sum -= remove; result = (double) sum / n; } return result; } } /** * Your MovingAverage object will be instantiated and called as such: * MovingAverage obj = new MovingAverage(size); * double param_1 = obj.next(val); */
I liked the concept of implementing it through the Queue.
ReplyDelete