[LeetCode] 362. Design Hit Counter

[grandyang]

 

Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time.

Example:

HitCounter counter = new HitCounter();

// hit at timestamp 1.
counter.hit(1);

// hit at timestamp 2.
counter.hit(2);

// hit at timestamp 3.
counter.hit(3);

// get hits at timestamp 4, should return 3.
counter.getHits(4);

// hit at timestamp 300.
counter.hit(300);

// get hits at timestamp 300, should return 4.
counter.getHits(300);

// get hits at timestamp 301, should return 3.
counter.getHits(301); 

Follow up:
What if the number of hits per second could be very large? Does your design scale?

Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.

 

这道题让我们设计一个点击计数器，能够返回五分钟内的点击数，提示了有可能同一时间内有多次点击。由于操作都是按时间顺序的，下一次的时间戳都会大于等于本次的时间戳，那么最直接的方法就是用一个队列queue，每次点击时都将当前时间戳加入queue中，然后在需要获取点击数时，我们从队列开头开始看，如果开头的时间戳在5分钟以外了，就删掉，直到开头的时间戳在5分钟以内停止，然后返回queue的元素个数即为所求的点击数，参见代码如下：

 

解法一：

class HitCounter {
public:
    /** Initialize your data structure here. */
    HitCounter() {}
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        q.push(timestamp);
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        while (!q.empty() && timestamp - q.front() >= 300) {
            q.pop();
        }
        return q.size();
    }

private:
    queue<int> q;
};

 

下面这种方法和上面的方法很像，用了一个数组保存所有的时间戳，然后要返回点击数时，只需要从开头找到第一个在5分钟的时间戳的坐标，然后用数组总长度减去这个坐标即可，和上面的方法不同的是，这个方法不删掉之前的时间戳，缺点是会很占空间，而且越到后面效率越低，参见代码如下：

 

解法二：

class HitCounter {
public:
    /** Initialize your data structure here. */
    HitCounter() {}

    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        v.push_back(timestamp);
    }

    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        int i, j;
        for (i = 0; i < v.size(); ++i) {
            if (v[i] > timestamp - 300) {
                break;
            }
        }
        return v.size() - i;
    }

private:
    vector<int> v;
};

 

由于Follow up中说每秒中会有很多点击，下面这种方法就比较巧妙了，定义了两个大小为300的一维数组times和hits，分别用来保存时间戳和点击数，在点击函数中，将时间戳对300取余，然后看此位置中之前保存的时间戳和当前的时间戳是否一样，一样说明是同一个时间戳，那么对应的点击数自增1，如果不一样，说明已经过了五分钟了，那么将对应的点击数重置为1。那么在返回点击数时，我们需要遍历times数组，找出所有在5分中内的位置，然后把hits中对应位置的点击数都加起来即可，参见代码如下：

 

解法三：

class HitCounter {
public:
    /** Initialize your data structure here. */
    HitCounter() {
        times.resize(300);
        hits.resize(300);
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        int idx = timestamp % 300;
        if (times[idx] != timestamp) {
            times[idx] = timestamp;
            hits[idx] = 1;
        } else {
            ++hits[idx];
        }
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        int res = 0;
        for (int i = 0; i < 300; ++i) {
            if (timestamp - times[i] < 300) {
                res += hits[i];
            }
        }
        return res;
    }

private:
    vector<int> times, hits;
};

 

类似题目：

Logger Rate Limiter

 

参考资料：

https://leetcode.com/problemset/algorithms/

https://leetcode.com/discuss/109492/java-solution-easy-to-understand

https://leetcode.com/discuss/109489/simple-java-solution-with-explanation

https://leetcode.com/discuss/109499/super-easy-design-hit-gethits-fancy-data-structure-is-needed

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

方法3 只需要一个hits的vector就好， times只需要记录一个初始时间， 如果timestamp - time0 >=300, time0 = timestamp-299， 并把小于这个时间的全部清掉; >=600, 就全部清零， 用一个total来帮助统计

class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() {
time0 = 0;
total = 0;
counter.resize(300, 0);
}

/** Record a hit.
    @param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
    getHits(timestamp);
    int idx = timestamp%300;
    //printf("%d %d\n", idx, counter.size());
    ++counter[idx];
    ++total;
}

/** Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
    if(timestamp - time0 >=600){
        fill(counter.begin(), counter.end(), 0);
        total =0; 
        time0 = timestamp-300+1;
    }
    if(timestamp - time0 >= 300){
        int start = time0% 300;
        int end = timestamp%300+1;
        if(end < start) end += 300;
        for(int k = start; k < end; ++k){
            int idx = k % 300;
            //printf("time0 %d reduce %d %d\n", time0, idx, total);
            total -= counter[idx];
            counter[idx] = 0;
        }
        time0 = timestamp-300+1;
    }
    return total;
}
vector<int> counter;
int total;
int time0;

};