给定一个整数数据流和一个窗口大小,根据该滑动窗口的大小,计算滑动窗口里所有数字的平均值。
实现 MovingAverage
类:
MovingAverage(int size)
用窗口大小size
初始化对象。double next(int val)
成员函数next
每次调用的时候都会往滑动窗口增加一个整数,请计算并返回数据流中最后size
个值的移动平均值,即滑动窗口里所有数字的平均值。
示例:
输入: inputs = ["MovingAverage", "next", "next", "next", "next"] inputs = [[3], [1], [10], [3], [5]] 输出: [null, 1.0, 5.5, 4.66667, 6.0] 解释: MovingAverage movingAverage = new MovingAverage(3); movingAverage.next(1); // 返回 1.0 = 1 / 1 movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2 movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3 movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3
提示:
1 <= size <= 1000
-105 <= val <= 105
- 最多调用
next
方法104
次
注意:本题与主站 346 题相同: https://leetcode.cn/problems/moving-average-from-data-stream/
方法一:循环数组
方法二:队列
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)
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)
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);
*/
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);
*/
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);
*/
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);
*/
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)))
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
/**
* Your MovingAverage object will be instantiated and called as such:
* obj := Constructor(size);
* param_1 := obj.Next(val);
*/
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);
*/