C++ solution using a queue, calculate average in O(1)


  • 0
    M
    class MovingAverage {
    private:
        queue<int> q;
        int queue_size;
        int sum;
    public:
        /** Initialize your data structure here. */
        MovingAverage(int size) {
            
            queue_size = size;
            sum = 0;
    
        }
        
        double next(int val) {
    
            if(q.size() < queue_size)
            {
                q.push(val);
                sum = sum + val;
            }
            else if(q.size() == queue_size)
            {
                int top = q.front();
                sum = sum - top;
                q.pop();
                q.push(val);
                sum = sum + val;
            }
            
            if(q.size() > 0)
                return double(sum)/(q.size());
            else
                return 0;
        }
    };
    
    /**
     * Your MovingAverage object will be instantiated and called as such:
     * MovingAverage obj = new MovingAverage(size);
     * double param_1 = obj.next(val);
     */

Log in to reply
 

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