c++ 计算五分钟内的平均值

一个面试题。题目： 计算五分钟内的平均值。 一个函数接收数值，一次接收一个。不确定下一个数值来的时间。你需要做的就是设计一个函数 mean()，计算从现在开始到五分钟前，接收到的所有数值的平均值

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
using namespace std::chrono;

long long currentTime() {
    return duration_cast<microseconds>(steady_clock::now().time_since_epoch()).count();
}

class MeanLimiter {
private:
    vector<long long> data;
    vector<long long> prefixSum;

    int sz = 0;
    long long last = -1;

    void enlargeIfNeed() {
        if (sz >= data.size()) {
            int new_sz = data.size() * 2 + 4;
            if (data.size() > 1000) {
                new_sz = data.size() + 1000;
            }
            data.resize(new_sz);
            prefixSum.resize(new_sz);
            cout << "enlarge " << new_sz << "\n";
        }
    }

public:
    void push(int value) {
        auto t = currentTime();
        last = t;
        long long pre = 0;
        enlargeIfNeed();
        data[sz] = t;
        if (sz > 0) {
            pre = prefixSum[sz - 1];
        }
        prefixSum[sz] = pre + value;
        ++sz;
    }

    void moveIfNeed(int index) {
        if (index * 2 >= sz + 4 || index > 1000) {
            cout << "\ttry move\t" << index << "\t" << sz - index << "\n";
            long long pre = prefixSum[index - 1];
            for (int x = 0; x + index < sz; x++) {
                data[x] = data[x + index];
                prefixSum[x] = prefixSum[x + index] - pre;
            }
            sz -= index;
        }
    }

    double mean() {
        if (-1 == last) {
            return -1;
        }
        long long start = last - 3e6;
        // 二分查找第一个大于等于的下标
        int index = lower_bound(data.begin(), data.begin() + sz, start) - data.begin();
        int count = sz - index;
        long long sum = prefixSum[sz - 1];
        if (index > 0) {
            sum -= prefixSum[index - 1];
            moveIfNeed(index);
            cout << "\t index: " << index << "\t";
        }
        return (sum * 1.0) / count;
    }

};

int main() {
    MeanLimiter mean;
    for (int i = 0; i < 10; i++) {
        int v = random() % 5 + 1;
        mean.push(v);
        cout << i << "\t" << v << "\t" << mean.mean() << endl;
        int st = random() % 3000000;
        this_thread::sleep_for(microseconds(st));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#输出

c++ 计算五分钟内的平均值
c++ 计算五分钟内的平均值
c++ 计算五分钟内的平均值
c++ 计算五分钟内的平均值
c++ 计算五分钟内的平均值
c++ 计算五分钟内的平均值
c++ 计算五分钟内的平均值
c++ 计算五分钟内的平均值
c++ 计算五分钟内的平均值
c++ 计算五分钟内的平均值