# 362 Design Hit Counter
設計一個計算點擊的程式。
包含兩個函式：getHits()可取得某timestamp五分鐘之內的總hit數量，hit()表示在某時間點有人點擊，要加入記錄。
此題有兩種存法：
- Queue: 另創一個class叫Record，成員有timestamp和點擊次數，精確度可以無限大。
- Arrays: 一個array存timestamp，另一個存點擊次數。時間複雜度比較低。
Queue
宣告一個Queue<Record>來記錄所有timestamp的點擊次數，
還有一個int curHit記錄整個queue裡面的total hit.
- hit(): 每次點擊，就先把queue中不是五分鐘之內的記錄poll出來，再檢查此timestamp是否已經在queue中，若是，直接把該記錄的hitCount++，若否，加入一個新紀錄。
- getHits(): 用queue.peek()檢查queue中有沒有不是五分鐘之內的記錄，如果有，要把它們poll出來，並且從curHit中減掉。
/***
use a queue to save all record
for infinite granularity
***/
public class HitCounter {
public class Record{
int time;
int hitCount;
public Record(int t, int c){
this.time = t;
this.hitCount = c;
}
}
Queue<Record> queue;
int curHit;
/** Initialize your data structure here. */
public HitCounter() {
queue = new LinkedList<Record>();
curHit = 0;
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
//remove all the element which is not within 5 mins
//if queue is not empty && timestamp == queue.peek().time
// queue.peek().hitCount += 1;
//else
// if timestamp - queue.peek().time >=300
// queue.poll();
// queue.add(new Record(timestamp, 1))
//curHit++;
while(!queue.isEmpty() && queue.peek().time <= timestamp - 300) {
curHit -= queue.poll().hitCount;
}
if(!queue.isEmpty() && timestamp == queue.peek().time)
queue.peek().hitCount += 1;
else{
queue.add(new Record(timestamp, 1));
}
curHit++;
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
//while the queue is not empty, and the first element in the queue is not within 5 min
// take it out from current hit count and poll the element
while(!queue.isEmpty() && queue.peek().time <= timestamp - 300) {
curHit -= queue.poll().hitCount;
}
return curHit;
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
Array
宣告兩個array，一個存timestamp，另一個存hit，time[i]的點擊次數即為hit[i]。
- hit(): the index of time array is timestamp % 300. Why? for example, when timestamp = 301, the hit at timestamp = 1 is not within 5 min anymore, should be discarded. 如果timestamp == time[index]，hit[index]++，否則就要更新time[index]，hit[index]從1開始累計。
- getHits(): for each element in time array, 如果time[i]是在timestamp的五分鐘之內，即把hit[i]加到total裡面。
/***
use 2 arrays to save time and hit
***/
public class HitCounter {
//create an array of size 300 to save "time"
//create an array of size 300 to save "hit"
int[] time;
int[] hit;
/** Initialize your data structure here. */
public HitCounter() {
//initialize the size of time and hitCount array
time = new int[300];
hit = new int[300];
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
//int index = timestamp % 300,
//for example, when timestamp= 301,
//the hit at timestamp = 1 is not in 5 min, should be discarded.
//if timestamp equals to time[index], we should keep incrementing hit[index]
//else start hit[index] from 1, update time[index]=timestamp
int index = timestamp % 300;
if(timestamp == time[index]){
hit[index]++;
}
else{
//if having multiple thread, need a lock()
hit[index] = 1;
time[index] = timestamp;
}
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
//int total to save the answer
//for each element in hit[]
// if timestamp - time[i] < 300, add hit[i] to total
int total = 0;
for(int i=0; i<300; i++){
if(timestamp - time[i] < 300){
total += hit[i];
}
}
return total;
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/