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
代码
Approach #1 Array or List
class MovingAverage {
int size;
LinkedList<Integer> queue = new LinkedList<Integer>();
/** Initialize your data structure here. */
public MovingAverage(int size) {
this.size = size;
}
public double next(int val) {
queue.add(val);
int windowSum = 0;
for (int i = Math.max(0, queue.size() - size); i < queue.size(); i++) {
windowSum += (int)queue.get(i);
}
return windowSum * 1.0 / Math.min(queue.size(), size);
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/
Approach #2 Double-ended Queue
class MovingAverage {
int size, windowsUM = 0, count = 0;
Deque queue = new ArrayDeque<Integer>();
public MovingAverage(int size) {
this.size = size;
}
public double next(int val) {
count++;
queue.add(val);
int tail = count > size ? (int)queue.poll() : 0;
windowSum = windowSum - tail + val;
return windowSum * 1.0 / Math.min(size, count);
}
}
Approach #3 Circular Queue with array
class MovingAverage {
int size, head = 0, windowSum = 0, count = 0;
int[] queue;
public MovingAverage(int size) {
this.size = size;
queue = new int[size];
}
public double next(int val) {
++count;
// calculate the new sum by shifting the window
int tail = (head + 1) % size;
windowSum = windowSum - queue[tail] + val;
// move on to the next head
head = (head + 1) % size;
queue[head] = val;
return windowSum * 1.0 / Math.min(size, count);
}
}