Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
For example:
1
2
3
4
5
|
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
|
Solution:
Use a Queue serve as a sliding window, and also maintain the current sum inside of the window.
Java实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public class {
private Queue<Integer> queue;
private int prevsum;
private int size;
public (int size) {
this.queue = new LinkedList<Integer>();
this.size = size;
this.prevsum = 0;
}
public double next(int val) {
if (queue.size() == this.maxSize)
this.prevsum -= this.queue.remove();
this.queue.add(val);
this.prevsum += val;
return this.prevsum / this.queue.size();
}
}
|
C语言实现:
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
28
|
typedef struct {
int *queue;
double prevsum;
int tail;
int count;
int size;
} MovingAverage;
MovingAverage* movingAverageCreate(int size) {
MovingAverage* obj = (MovingAverage*)malloc(sizeof(MovingAverage));
obj->queue = (int*)malloc(size * sizeof(int));
obj->prevsum = 0.0;
obj->tail = 0;
obj->count = 0;
obj->size = size;
}
double movingAverageNext(MovingAverage* obj, int val) {
if (obj->count==obj->size) {
obj->prevsum -= obj->queue[obj->tail];
} else {
obj->count++;
}
obj->queue[obj->tail] = val;
obj->tail = (obj->tail + 1) % obj->size;
obj->prevsum += val;
return obj->prevsum/obj->count;
}
|
近期评论