MovingAverageFromDataStream [source code]

public class MovingAverageFromDataStream {
    private double[] data;
    private int pointer;
    private int length;
    private final int size;

    /** Initialize your data structure here. */
    public MovingAverageFromDataStream(int size) {
        data = new double[size];
        this.size = size;
    }

    public double next(int val) {
        double res = 0.0;           // double needs to be initialized
        data[pointer] = val;
        pointer = (pointer + 1) % size;
        if (length >= size - 1) {
            if (length == size - 1) length++;
            for (int i = 0; i < size; i++) res += data[i];
            return res / size;
        }
        length++;
        for (int i = 0; i < length; i++) res += data[i];
        return res / length;
    }

    public static void main(String[] args) {
        MovingAverageFromDataStream m = new MovingAverageFromDataStream(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);
 */

刚开始写这个算法的时候, 总是给 pointer 的作用搞混淆, 到底应该 point next position to insert, 还是the position that last insertion happened?

其实这个是无所谓的, 不要在这种不重要的问题上浪费时间, 随便选一个, 然后记住你选的代表的是什么意思就行了, 然后move on;
比如我这里就选择pointer is the position to do next insertion;类似的, 如果是data 满了的情况下, lenght 应该是3还是2? 自己选一个就行了, 我这里选的是3;

这里一个比较好的注意点: length==0 跟 pointer==0表达的意思其实是相差很大的, 不知道你注意到没有;

看起来很简单的一个问题, 最后结果居然还是花了不少的时间. 其实算法核心还是很简单, 就是针对不同的 length(current number of entries filled)进行不同的 conditional 操作. 代码本身完成的其实就是对不同的branch 进行了一定的整合而已;

最后的速度是188ms, 18%. 这个还是挺令人失望的.

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