[LeetCode] 346. Moving Average from Data Stream 从数据流中移动平均值

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 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.html

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) / 3java

给一个整数流和一个窗口,计算在给定大小的窗口里的数字的平均值。python

解法:队列queue,用一个queue记录进入窗口的整数。当流进窗口的整数不足时,计算全部窗口内的数字和返回,当进入窗口的整数多于窗口大小时,移除最早进入窗口的整数,新的整数进入queue,而后计算窗口内的整数和。app

Java:post

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);
 */  

Java:this

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;
    }
 
    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();
            double minus = (double)head/this.size;
            queue.offer(val);
            double add = (double)val/this.size;
            avg = avg + add - minus;
            return avg;
        }
    }
}  

Python:url

# Time:  O(1)
# Space: O(w)
from collections import deque

class MovingAverage(object):
    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.__size = size
        self.__sum = 0
        self.__q = deque([])

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        if len(self.__q) == self.__size:
            self.__sum -= self.__q.popleft()
        self.__sum += val
        self.__q.append(val)
        return 1.0 * self.__sum / len(self.__q)


# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)  

C++:htm

class MovingAverage {
public:
    MovingAverage(int size) {
        this->size = size;
        sum = 0;
    }
    
    double next(int val) {
        if (q.size() >= size) {
            sum -= q.front(); q.pop();
        }
        q.push(val);
        sum += val;
        return sum / q.size();
    }
    
private:
    queue<int> q;
    int size;
    double sum;
};

  

 

All LeetCode Questions List 题目汇总