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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class MovingAverage:
def __init__(self, size: int):
self.arr = [0] * size
self.s = 0
self.cnt = 0
def next(self, val: int) -> float:
idx = self.cnt % len(self.arr)
self.s += val - self.arr[idx]
self.arr[idx] = val
self.cnt += 1
return self.s / min(self.cnt, len(self.arr))
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class MovingAverage {
private int[] arr;
private int s;
private int cnt;
public MovingAverage(int size) {
arr = new int[size];
}
public double next(int val) {
int idx = cnt % arr.length;
s += val - arr[idx];
arr[idx] = val;
++cnt;
return s * 1.0 / Math.min(cnt, arr.length);
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class MovingAverage {
public:
MovingAverage(int size) {
arr.resize(size);
}
double next(int val) {
int idx = cnt % arr.size();
s += val - arr[idx];
arr[idx] = val;
++cnt;
return (double) s / min(cnt, (int) arr.size());
}
private:
vector<int> arr;
int cnt = 0;
int s = 0;
};
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage* obj = new MovingAverage(size);
* double param_1 = obj->next(val);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| type MovingAverage struct {
arr []int
cnt int
s int
}
func Constructor(size int) MovingAverage {
arr := make([]int, size)
return MovingAverage{arr, 0, 0}
}
func (this *MovingAverage) Next(val int) float64 {
idx := this.cnt % len(this.arr)
this.s += val - this.arr[idx]
this.arr[idx] = val
this.cnt++
return float64(this.s) / float64(min(this.cnt, len(this.arr)))
}
/**
* Your MovingAverage object will be instantiated and called as such:
* obj := Constructor(size);
* param_1 := obj.Next(val);
*/
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| 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);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 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);
*/
|
