Lintcode 642 · Moving Average from Data Stream

642 · Moving Average from Data Stream
Algorithms
Easy
Description
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Example
Example 1:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1 // return 1.00000
m.next(10) = (1 + 10) / 2 // return 5.50000
m.next(3) = (1 + 10 + 3) / 3 // return 4.66667
m.next(5) = (10 + 3 + 5) / 3 // return 6.0000

解法1：用queue。

class MovingAverage {
public:
    /*
    * @param size: An integer
    */MovingAverage(int size) : _size(size), _sum(0.0) {
        
    }

    /*
     * @param val: An integer
     * @return:  
     */
    double next(int val) {
        q.push(val);
        _sum += val;
        if (q.size() > _size) {
            _sum -= q.front();
            q.pop();
        }
        return _sum / q.size();
    }
private:
    queue<int> q;
    int _size;
    double _sum;
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param = 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
28
29
30
31
32