【LetMeFly】 Low space consumption solution ： The finger of the sword Offer II 041. Average value of sliding window

Force button topic link ：https://leetcode.cn/problems/qIsx9U/

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

Be careful ： This topic and the main station 346  The question is the same ： https://leetcode-cn.com/problems/moving-average-from-data-stream/

Method 1 ： simulation

This problem can be simulated .

• use int size Record “ The sliding window ” Maximum size of
• use int sum Record “ The sliding window ” Sum of all values in
• use int num Record “ The sliding window ” Number of digits of

So what is used to simulate windows ？ In fact, using queues is a great choice .

But you can also see from this title , This solution mainly uses low space consumption to solve the problem , So I decided to use Static array To simulate a queue .

Because the length of the queue is fixed , So when we open up arrays , The size of the development is “ The sliding window ” The size is ok .

• use int* a Simulation queue
• use int loc Record the subscript of the element about to leave the team

private:
    int size;
    int sum;
    int num;
    int *a;  // Array
    int loc;  //  Which should be removed 

public:
    /** Initialize your data structure here. */
    MovingAverage(int size): size(size), sum(0), num(0), a(new int[size]), loc(0) {
    

    }

Direction “ The sliding window ” When adding new elements in , First, check whether the queue is full .

• If dissatisfied, add new elements
• If it is full, delete the old element and add a new element

if (num < size) {
      //  At first , The window hasn't been filled yet 
    sum += val;
    a[num++] = val;
    return ONE * sum / num;  //  among ONE yes double Type of 1
}
else {
    
    sum -= a[loc];
    sum += val;
    a[loc++] = val;
    loc %= size;
    return ONE * sum / num;
}

Running results ：

If you want to be more rigorous , It can be used during class destructions deletenew Out of the array

~MovingAverage() {
    
    delete[] a;
}

The running time has been reduced

• Time complexity $O(n)$, among $n$ Is the number of elements to add
• Spatial complexity $O(m)$, among $m$ yes “ The sliding window ” Size

AC Code

C++

const double ONE = 1;

class MovingAverage {
    
private:
    int size;
    int sum;
    int num;
    int *a;  // Array
    int loc;  //  Which should be removed 
public:
    /** Initialize your data structure here. */
    MovingAverage(int size): size(size), sum(0), num(0), a(new int[size]), loc(0) {
    

    }

    ~MovingAverage() {
    
        delete[] a;
    }
    
    double next(int val) {
    
        if (num < size) {
      //  At first , The window hasn't been filled yet 
            sum += val;
            a[num++] = val;
            return ONE * sum / num;
        }
        else {
    
            sum -= a[loc];
            sum += val;
            a[loc++] = val;
            loc %= size;
            return ONE * sum / num;
        }
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125819216