Monday, January 16, 2017

Leetcode/G家 -- 346. Moving Average from Data Stream (queue)

346. Moving Average from Data Stream(queue)
easy
https://leetcode.com/problems/moving-average-from-data-stream/

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

思路: queue size小于window size就是直接除。
           Adding num to queue till it reach window size(max Size) and adding to previous sum(save u from cost O(n) to traverse queue).  Once reached, remove the 1st element & subtract off previous sum, then add the new element  to queue (also recalculate sum)

Complexity: time O(1), space O(window size)

public class MovingAverage {
    private double previousSum = 0.0;
    private int maxSize;
    private Queue<Integer> currentWindow;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        currentWindow = new LinkedList<Integer>();
        maxSize = size;
    }
    
    public double next(int val) {
        if(currentWindow.size()==maxSize){
            previousSum -= currentWindow.remove();
        }
        currentWindow.add(val);
        previousSum += val;
        return previousSum/currentWindow.size();
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

No comments:

Post a Comment