Leaky Cauldron
0%

点击计数器

Posted on Edited on

题目(LeetCode #362)

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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?

题解

解法一

使用队列保存所有的 timestamp，获取点击数时将所有与当前时间戳相距 5 分钟以上的元素弹出，返回剩余队列长度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class HitCounter {
    private Queue<Integer> queue;

    public HitCounter() {
        queue = new ArrayDeque<>();
    }

    public void hit(int timestamp) {
        queue.add(timestamp);
    }

    public int getHits(int timestamp) {
        while (!queue.isEmpty() && timestamp - queue.peek() >= 300)
            queue.poll();

        return queue.size();
    }
}

解法二

对于 follow up 中的情况，可使用两个数组分别保存时间戳和点击次数，每次调用 hit 时将时间戳对 300 取余得到对应的索引，若该索引对应的时间戳与当前输入不同，则说明已超过 5 分钟。

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
class HitCounter {
    private int[] times, hits;

    public HitCounter() {
        times = new int[300];
        hits = new int[300];
    }

    public void hit(int timestamp) {
        int idx = timestamp % 300;
        if (times[idx] != timestamp) {
            times[idx] = timestamp;
            hits[idx] = 1;
        } else {
            hits[idx]++;
        }
    }

    public int getHits(int timestamp) {
        int cnt = 0;

        for (int i = 0; i < 300; i++) {
            if (timestamp - times[i] < 300) {
                cnt += hits[i];
            }
        }

        return cnt;
    }
}