MovingAverageFromDataStreamOPT2 [source code]

public class MovingAverageFromDataStreamOPT2 {
    private int currentSize;
    private int [] window;
    private int n, insert;
    private long sum;

    /** Initialize your data structure here. */
    public MovingAverageFromDataStreamOPT2(int size) {
        window = new int[size];
        insert = 0;
        sum = 0;
    }

    public double next(int val) {
        if (n < window.length)  n++;
        sum -= window[insert];
        sum += val;
        window[insert] = val;
        insert = (insert + 1) % window.length;

        return (double)sum / n;
    }

    public static void main(String[] args) {
        MovingAverageFromDataStreamOPT2 m = new MovingAverageFromDataStreamOPT2(3);
        int[] input1 = {1,10,3,5};
        for (int i : input1) System.out.println(m.next(i));
    }
}
/**
 * Your MovingAverageFromDataStream object will be instantiated and called as such:
 * MovingAverageFromDataStream obj = new MovingAverageFromDataStream(size);
 * double param_1 = obj.next(val);
 */

这个是另外一个最优解, 这个最优解类似于是我自己的版本的优化版本, 他优化的地方在于:

1. next 本身内部的逻辑大幅度简化.
2. 这个简化的完成是由他的另一个优化导致的: 他maintain the current sum. 这个我真的是没有想到, 但是是一个非常有用的优化. 一来可以明显提高速度(不用做除法了), 二来可以让 next 内部的逻辑大幅度简化;

这个题目还让我认识到, 不能光是看 submission 里面的最优解, discussion 里面的最优解也要看. submission 里面的最优解很可能是过时的, 比如这一题的 OPT1就是这样的. 不过discussion 里面的最优解, 往往是长时间一直被大家观察的, 所以能够做到 discussion的榜首的, 一般都是很好的答案;

为什么人家能够想到这里的maintain and update sum? 其实类似的想法, 在学两本算法书的时候是大概碰到过的, 不过并没有认真总结过. 当时就有点觉得, 这种用其他的变量都能够算出来的东西,为什么要 maintain. 现在看来就是很有意义的, 对于算法加速非常有意义;

Problem Description

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

For example,
MovingAverageFromDataStream m = new MovingAverageFromDataStream(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
Hide Company Tags Google
Hide Tags Design Queue