2 Java solutions, Queue vs Array


  • 0
    M

    Method 1: Using Queue
    Time: O(1) for hit() and O(n) for getHits().

    If the hitting times is less than 300 per 5 minutes, or hit() is frequent while getHits() is rare, Method 1 is better.

    public class HitCounter {
        Queue<Integer> que;
        int counter = 0;
        /** Initialize your data structure here. */
        public HitCounter() {
            que = new LinkedList<>();
        }
        
        //O(1)
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            que.offer(timestamp);
            counter++;
        }
        
        //O(n)
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
            clearOld(timestamp);
            return counter;
        }
        //O(n)
        private void clearOld(int timestamp){
            int limit = timestamp - 300;
            while(!que.isEmpty() && que.peek()<=limit){
                que.poll();
                counter--;
            }
        }   
    }
    

    Method 2: Using array
    Time: O(300) = O(1) for hit() and getHits().

    public class HitCounter {
        final static int N = 300;
        private int[] arr;
        private int lastTime;
        private int p;
        private int counter;
        
        /** Initialize your data structure here. */
        public HitCounter() {
            arr = new int[N];
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            clearOld(timestamp);
            arr[p]++;
            counter++;
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
            clearOld(timestamp);
            return counter;
        }
        //O(300) = O(1)
        private void clearOld(int timestamp){
            int n = Math.min(timestamp-lastTime ,N);
            for(int i=0; i<n; i++){
                p = (p+1)%N;
                counter -= arr[p];
                arr[p] = 0;
            }
            lastTime = timestamp;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.