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
给一个整数流和一个窗口，计算在给定大小的窗口里的数字的平均值。
解法：队列queue，用一个queue记录进入窗口的整数。当流进窗口的整数不足时，计算所有窗口内的数字和返回，当进入窗口的整数多于窗口大小时，移除最先进入窗口的整数，新的整数进入queue，然后计算窗口内的整数和。
Java:
public class MovingAverage {
private double previousSum = 0.0;
private int maxSize;
private Queue<Integer> currentWindow;
/** Initialize your data structure here. */
public MovingAverage(int size) {
currentWindow = new LinkedList<Integer>();
maxSize = size;
}
public double next(int val) {
if(currentWindow.size()==maxSize){
previousSum -= currentWindow.remove();
}
currentWindow.add(val);
previousSum += val;
return previousSum/currentWindow.size();
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/
Java:
public class MovingAverage {
LinkedList<Integer> queue;
int size;
double avg;
/** Initialize your data structure here. */
public MovingAverage(int size) {
this.queue = new LinkedList<Integer>();
this.size = size;
}
public double next(int val) {
if(queue.size()<this.size){
queue.offer(val);
int sum=0;
for(int i: queue){
sum+=i;
}
avg = (double)sum/queue.size();
return avg;
}else{
int head = queue.poll();
double minus = (double)head/this.size;
queue.offer(val);
double add = (double)val/this.size;
avg = avg + add - minus;
return avg;
}
}
}
Python:
# Time: O(1)
# Space: O(w)
from collections import deque class MovingAverage(object):
def __init__(self, size):
"""
Initialize your data structure here.
:type size: int
"""
self.__size = size
self.__sum = 0
self.__q = deque([]) def next(self, val):
"""
:type val: int
:rtype: float
"""
if len(self.__q) == self.__size:
self.__sum -= self.__q.popleft()
self.__sum += val
self.__q.append(val)
return 1.0 * self.__sum / len(self.__q) # Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)
C++:
class MovingAverage {
public:
MovingAverage(int size) {
this->size = size;
sum = 0;
}
double next(int val) {
if (q.size() >= size) {
sum -= q.front(); q.pop();
}
q.push(val);
sum += val;
return sum / q.size();
}
private:
queue<int> q;
int size;
double sum;
};