Question

Formatted question description: https://leetcode.ca/all/346.html

 346	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

 @tag-design
 @tag-stream

Algorithm

This first-in, first-out feature is most suitable for using queues, and we also need a double variable sum to record the sum of all current numbers.

After entering this new number,

  • If the limit is not exceeded, sum plus this number,
  • If it exceeds, then sum first subtracts the earliest number, then adds this number, and then returns the number of sum divided by the queue

Code

Java

  • import java.util.LinkedList;
    
    public class Moving_Average_from_Data_Stream {
    
        public static void main(String[] args) {
            Moving_Average_from_Data_Stream out = new Moving_Average_from_Data_Stream();
            MovingAverage m = out.new MovingAverage(3);
    
            System.out.println(m.next(1));
            System.out.println(m.next(10));
            System.out.println(m.next(3));
            System.out.println(m.next(5));
        }
    
        public class MovingAverage {
            LinkedList<Integer> queue;
            int size;
            double avg;
    
            /** Initialize your data structure here. */
            public MovingAverage(int size) {
                this.queue = new LinkedList<Integer>();
                this.size = size;
            }
    
            /** API: Return moving average. */
            public double next(int val) {
                if (queue.size() < this.size) {
                    queue.offer(val);
                    int sum = 0;
                    for (int i : queue) {
                        sum += i;
                    }
                    avg = (double) sum / queue.size();
    
                    return avg;
                } else {
                    int head = queue.poll();
                    queue.offer(val);
    
                    double minus = (double) head / this.size;
                    double add = (double) val / this.size;
    
                    avg = avg + add - minus; // math
    
                    return avg;
                }
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/moving-average-from-data-stream/
    // Time:
    //     MovingAverage: O(1)
    //     next: O(1)
    // Space: O(S)
    class MovingAverage {
    private:
        queue<int> q;
        int size, sum = 0;
    public:
        MovingAverage(int size) : size(size) { }
        double next(int val) {
            q.push(val);
            sum += val;
            if (q.size() > size) {
                sum -= q.front();
                q.pop();
            }
            return (double)sum / q.size();
        }
    };
    
  • from collections import deque
    
    
    class MovingAverage(object):
    
      def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.windowSize = size
        self.windowSum = 0.0
        self.data = deque([])
    
      def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        self.windowSum += val
        data = self.data
    
        leftTop = 0
        if len(data) >= self.windowSize:
          leftTop = data.popleft()
        data.append(val)
    
        self.windowSum -= leftTop
        if len(data) < self.windowSize:
          return self.windowSum / len(data)
        return self.windowSum / self.windowSize
    
    # Your MovingAverage object will be instantiated and called as such:
    # obj = MovingAverage(size)
    # param_1 = obj.next(val)
    
    

All Problems

All Solutions