Java O(1) time solution.


  • 34
    S

    The idea is to keep the sum so far and update the sum just by replacing the oldest number with the new entry.

    public class MovingAverage {
        private int [] window;
        private int n, insert;
        private long sum;
        
        /** Initialize your data structure here. */
        public MovingAverage(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;
        }
    }

  • 11
        Queue<Integer> q;
        double sum = 0;
        int size;
    
        public MovingAverage(int s) {
            q = new LinkedList();
            size = s;
        }
        
        public double next(int val) {
            if(q.size() == size){
                sum = sum - q.poll();
            }
            q.offer(val);
            sum += val;
            return sum/q.size();
        }

  • 0
    M

    @hot13399
    To prevent overflow,

    double sum = 0;

  • 0
    V

    Perfect solution.


  • 0

    @hot13399 very nifty way to simulate a circular buffer through a bounded queue!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.