java solution o(1) hit() and O(log n) solution. binary search is used.


  • 0
    W
    public class HitCounter {
        List<Integer> set;
        /** Initialize your data structure here. */
        public HitCounter() {
            set = new ArrayList<>();
        }
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            set.add(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 left = 0;
            int right = set.size()-1;
            while (left <= right) {
                int mid = left + (right-left)/2;
                if (set.get(mid) >= (timestamp-299)) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
    } 
            return set.size()-left;
        }
    } 
    /**
     * Your HitCounter object will be instantiated and called as such:
     * HitCounter obj = new HitCounter();
     * obj.hit(timestamp);
     * int param_2 = obj.getHits(timestamp);
     */
    
    

Log in to reply
 

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