Description
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Implement the MovingAverage class:
MovingAverage(int size) Initializes the object with the size of the window size.double next(int val) Returns the moving average of the last size values of the stream.
Example 1:
Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]
Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3
Constraints:
1 <= size <= 1000-105 <= val <= 105- At most
104 calls will be made to next.
Solutions
Solution 1: Circular Array
We define a variable s to calculate the sum of the last size elements, and a variable cnt to record the total number of current elements. Additionally, we use an array data of length size to record the value of each element at each position.
When calling the next function, we first calculate the index i where val should be stored, then update the sum s, set the value at index i to val, and increment the element count by one. Finally, we return the value of s⁄min(cnt, size).
The time complexity is O(1), and the space complexity is O(n), where n is the integer size given in the problem.
PythonJavaC++GoTypeScript
class MovingAverage:
def __init__(self, size: int):
self.s = 0
self.data = [0] * size
self.cnt = 0
def next(self, val: int) -> float:
i = self.cnt % len(self.data)
self.s += val - self.data[i]
self.data[i] = val
self.cnt += 1
return self.s / min(self.cnt, len(self.data))
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)(code-box)
class MovingAverage {
private int s;
private int cnt;
private int[] data;
public MovingAverage(int size) {
data = new int[size];
}
public double next(int val) {
int i = cnt % data.length;
s += val - data[i];
data[i] = val;
++cnt;
return s * 1.0 / Math.min(cnt, data.length);
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/(code-box)
class MovingAverage {
public:
MovingAverage(int size) {
data.resize(size);
}
double next(int val) {
int i = cnt % data.size();
s += val - data[i];
data[i] = val;
++cnt;
return s * 1.0 / min(cnt, (int) data.size());
}
private:
int s = 0;
int cnt = 0;
vector<int> data;
};
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage* obj = new MovingAverage(size);
* double param_1 = obj->next(val);
*/(code-box)
type MovingAverage struct {
s int
cnt int
data []int
}
func Constructor(size int) MovingAverage {
return MovingAverage{
data: make([]int, size),
}
}
func (this *MovingAverage) Next(val int) float64 {
i := this.cnt % len(this.data)
this.s += val - this.data[i]
this.data[i] = val
this.cnt++
return float64(this.s) / float64(min(this.cnt, len(this.data)))
}
/**
* Your MovingAverage object will be instantiated and called as such:
* obj := Constructor(size);
* param_1 := obj.Next(val);
*/(code-box)
class MovingAverage {
private s: number = 0;
private cnt: number = 0;
private data: number[];
constructor(size: number) {
this.data = Array(size).fill(0);
}
next(val: number): number {
const i = this.cnt % this.data.length;
this.s += val - this.data[i];
this.data[i] = val;
this.cnt++;
return this.s / Math.min(this.cnt, this.data.length);
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* var obj = new MovingAverage(size)
* var param_1 = obj.next(val)
*/(code-box)
Solution 2: Queue
We can use a queue q to store the last size elements, and a variable s to record the sum of these size elements.
When calling the next function, we first check if the length of the queue q is equal to size. If it is, we dequeue the front element of the queue q and update the value of s. Then we enqueue val and update the value of s. Finally, we return the value of s⁄len(q).
The time complexity is O(1), and the space complexity is O(n), where n is the integer size given in the problem.
PythonJavaC++GoTypeScript
class MovingAverage:
def __init__(self, size: int):
self.n = size
self.s = 0
self.q = deque()
def next(self, val: int) -> float:
if len(self.q) == self.n:
self.s -= self.q.popleft()
self.q.append(val)
self.s += val
return self.s / len(self.q)
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)(code-box)
class MovingAverage {
private Deque<Integer> q = new ArrayDeque<>();
private int n;
private int s;
public MovingAverage(int size) {
n = size;
}
public double next(int val) {
if (q.size() == n) {
s -= q.pollFirst();
}
q.offer(val);
s += val;
return s * 1.0 / q.size();
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/(code-box)
class MovingAverage {
public:
MovingAverage(int size) {
n = size;
}
double next(int val) {
if (q.size() == n) {
s -= q.front();
q.pop();
}
q.push(val);
s += val;
return (double) s / q.size();
}
private:
queue<int> q;
int s = 0;
int n;
};
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage* obj = new MovingAverage(size);
* double param_1 = obj->next(val);
*/(code-box)
type MovingAverage struct {
q []int
s int
n int
}
func Constructor(size int) MovingAverage {
return MovingAverage{n: size}
}
func (this *MovingAverage) Next(val int) float64 {
if len(this.q) == this.n {
this.s -= this.q[0]
this.q = this.q[1:]
}
this.q = append(this.q, val)
this.s += val
return float64(this.s) / float64(len(this.q))
}
/**
* Your MovingAverage object will be instantiated and called as such:
* obj := Constructor(size);
* param_1 := obj.Next(val);
*/(code-box)
class MovingAverage {
private q: number[] = [];
private s: number = 0;
private n: number;
constructor(size: number) {
this.n = size;
}
next(val: number): number {
if (this.q.length === this.n) {
this.s -= this.q.shift()!;
}
this.q.push(val);
this.s += val;
return this.s / this.q.length;
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* var obj = new MovingAverage(size)
* var param_1 = obj.next(val)
*/(code-box)
