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