leetcode解题: Moving Average from Data Stream (346)

发表于 | 分类于

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

For example,
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

解法1：O(1) Computation and O(N) space

需要考虑每次计算运用上次的结果，由于平均值是Sum / Size, 如果维护average的值的话不方便重复利用已经计算过的值，所以我们可以考虑维护一个当前的Sum. 最后需要计算average的时候就把sum除以当前的数字个数。

数据结构： 考虑使用queue, 用到的操作是queue.front(), queue.pop() 和queue.push(item)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//C++
  class MovingAverage {
  private:
      queue<int> data;
      int sum;
      int msize;
  public:
      MovingAverage(int size) {
          msize = size;
          sum = 0;
      }
      double next(int val) {
          if (data.size() == msize) {
              sum -= data.front();
              data.pop();
          }
          data.push(val);
          sum += val;
          return (double)sum / data.size();      
      }
  };