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)

346 - Moving Average from Data Stream

Question

Algorithm

Code

All Problems

All Solutions