java - 无需任何特殊数据结构即可计算移动平均线

我最近接受了一次面试，在面试中，我需要计算一段时间内的移动平均值。我提出了下面的解决方案，但面试官说他希望我不需要任何特殊的数据结构，因为DS会占用一些空间在没有任何数据结构的情况下，还有其他更好的方法可以做到这一点吗？

public class MovingAverage {
  private final Queue<BigDecimal> window = new ArrayDeque<>();
  private final int period;
  private BigDecimal sum = BigDecimal.ZERO;

  public MovingAverage(int period) {
    this.period = period;
  }

  public void add(BigDecimal num) {
    sum = sum.add(num);
    window.add(num);
    if (window.size() > period) {
      sum = sum.subtract(window.remove());
    }
  }

  public BigDecimal getAverage() {
    if (window.isEmpty())
      return BigDecimal.ZERO;
    BigDecimal divisor = BigDecimal.valueOf(window.size());
    return sum.divide(divisor, 2, RoundingMode.HALF_UP);
  }
}

最佳答案

固定长度数组是否算作“特殊数据结构”？如果不能，你可以这样做：

public class MovingAverage {
  private final BigDecimal[] window;
  private final int period;
  private int size;
  private int idx;
  private BigDecimal sum = BigDecimal.ZERO;

  public MovingAverage(int period) {
    this.period = period;
    window = new BigDecimal[period];
  }

  public void add(BigDecimal num) {
    if(size < period)
      size += 1;
    else
      sum = sum.subtract(window[idx]);

    sum = sum.add(num);
    window[idx++] = num;
    if(idx == period) idx = 0;
  }

  public BigDecimal getAverage() {
    if (size == 0)
      return BigDecimal.ZERO;
    BigDecimal divisor = BigDecimal.valueOf(size);
    return sum.divide(divisor, 2, RoundingMode.HALF_UP);
  }
}

关于java - 无需任何特殊数据结构即可计算移动平均线，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52581100/