Sword finger offer II 041. Average value of sliding window_____ Using queue / loop array implementation

The finger of the sword Offer II 041. Average value of sliding window

Given an integer data stream and a window size , Depending on the size of the sliding window , Calculate the average of all numbers in the sliding window .

Realization MovingAverage class ：

MovingAverage(int size) Use window size size Initialize object .
double next(int val) Member functions next An integer will be added to the sliding window every time , Please calculate and return the last... In the data stream size Moving average of values , That is, the average of all numbers in the sliding window .

Example ：

Input ：
inputs = [“MovingAverage”, “next”, “next”, “next”, “next”]
inputs = [[3], [1], [10], [3], [5]]
Output ：
[null, 1.0, 5.5, 4.66667, 6.0]

explain ：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

Tips ：

• 1 <= size <= 1000
• -105 <= val <= 105
• Call at most next Method 104 Time

Solution1（ Using the queue ）:

• Use queue structure directly ;

Code1:

/** * Your MovingAverage object will be instantiated and called as such: * MovingAverage obj = new MovingAverage(size); * double param_1 = obj.next(val); */
 class MovingAverage {
    

    Queue<Integer> queue;
    int len;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
    
        queue = new LinkedList<>();
        len = size;
    }
    
    public double next(int val) {
    
        if(queue.size() < len){
    
            queue.offer(val);
        }
        else{
    
            queue.poll();
            queue.offer(val);
        }

        double res = 0;
        //  Because the essence of queue is LinkedList, So you can't access directly according to subscripts like arrays 
        for(Integer one : queue){
    
            res += one;
        }
        return res / queue.size();
    }
}

Solution2（ Using the queue + Space for time preprocessing ）:

• Because of method 1, we need to calculate the average value every time , So we might as well create a variable directly res To maintain the total size of the elements in the queue , In this way, the average value of sliding window can be obtained directly when searching , also res Just execute every time next Always follow ++ that will do , No extra time ;

Code2:

/** * Your MovingAverage object will be instantiated and called as such: * MovingAverage obj = new MovingAverage(size); * double param_1 = obj.next(val); */
 class MovingAverage {
    

    Queue<Integer> queue;
    int len;
    double res;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
    
        queue = new LinkedList<>();
        len = size;
        res = 0;
    }
    
    public double next(int val) {
    
        if(queue.size() < len){
    
            queue.offer(val);
            res += val;
        }
        else{
    
            res -= queue.poll();
            queue.offer(val);
            res += val;
        }

        return res / queue.size();
    }
}

Solution3（ Use circular arrays to simulate queues + Space for time preprocessing ）:

• We can use circular arrays to simulate queues , Through the remainder operation, the array achieves the recyclable effect , To simulate the queue ;

Code3:

class MovingAverage {
    

    int[] rep;
    int front;
    int rear;
    int len;
    double res;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
    
        rep = new int[size];
        front = 0;
        rear = 0;
        res = 0;
    }
    
    public double next(int val) {
    
        //  First judge whether the queue is full 
        int repLen = rep.length;
        if(len < repLen){
    
            rep[rear] = val;
            rear = (rear + 1) % repLen;   //  The remainder has the effect of circulation 
            len++;
        }
        else{
    
            res -= rep[front];
            front = (front + 1) % repLen;
            rep[rear] = val;
            rear = (rear + 1) % repLen;
        }

        res += val;
        return res / len;
    }
}