Java concise O(1) hit and O(lgN) getHit Solution


  • 0
    W

    public class HitCounter {

    List<Integer> list = new ArrayList<>();
    Map<Integer, Integer> cumulativeCounter = new HashMap<>();
    int count;
    /** Initialize your data structure here. */
    public HitCounter() {
        count = 0;
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        list.add(timestamp);
        ++count;
        cumulativeCounter.put(timestamp, count);
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        int pos = binarySearch(timestamp - 300, 0, list.size() - 1);
        if (pos == -1) {
            return count;
        } else {
            return count - cumulativeCounter.get(list.get(pos));
        }
    }
    
    private int binarySearch(int timestamp, int left, int right) {
        if (left > right) {
            return left - 1;
        } 
        int mid = left + (right - left) / 2;
        if (list.get(mid) == timestamp) {
            return mid;
        } else if (list.get(mid) > timestamp) {
            return binarySearch(timestamp, left, mid - 1);
        } else {
            return binarySearch(timestamp, mid + 1, right);
        }
    }
    

    }


Log in to reply
 

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