Leetcode - Design Hit Counter（1）

look_w

My code:

    public class HitCounter {
        TreeMap<Integer, Integer> tree;
        private int counter = 0;
        /** Initialize your data structure here. */
        public HitCounter() {
            tree = new TreeMap<Integer, Integer>();
            tree.put(0, 0);
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            counter++;
            tree.put(timestamp, counter);
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        public int getHits(int timestamp) {
            int end = tree.floorKey(timestamp);
            int begin = timestamp - 300;
            if (begin <= 0) {
                return tree.get(end);
            }
            else {
                begin = tree.floorKey(begin);
                return tree.get(end) - tree.get(begin);
            }
        }
    }
     
    /**
     * Your HitCounter object will be instantiated and called as such:
     * HitCounter obj = new HitCounter();
     * obj.hit(timestamp);
     * int param_2 = obj.getHits(timestamp);
     */

自己用 TreeMap 写了出来。
然后研究了下TreeMap

他的 put, get, remove, containsKey, floor 都是 log(n) 时间复杂度。

所以这种实现方法， hit, getHits 的时间复杂度都是 O(log n)