05 August 2008
过去5mins的点击数
Queue
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
class HitCounter {
Queue<Integer> q = null;
/** Initialize your data structure here. */
public HitCounter() {
q = new LinkedList<Integer>();
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
q.offer(timestamp);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
while(!q.isEmpty() && timestamp - q.peek() >= 300) {
q.poll();
}
return q.size();
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
Cicular Array
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
class HitCounter {
int N;
int[] count;
int lastPosition;
int lastTime;
int sum;
/** Initialize your data structure here. */
public HitCounter() {
N = 300;
count = new int[N];
lastPosition = 0;
lastTime = 0;
sum = 0;
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
move(timestamp);
count[lastPosition]++;
sum++;
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
move(timestamp);
return sum;
}
void move(int timestamp){
int gap = Math.min(timestamp-lastTime, N);
for(int i=0; i<gap;i++){
lastPosition = (lastPosition+1)%N;
sum -= count[lastPosition];
count[lastPosition] = 0;
}
lastTime = timestamp;
}
}