use Collections.binarySearch hit() O(n) getHits() O(logn)


  • 0
    Q

    use binarySearch return value to calculate the hits within 5 min. hit() time = O(n) because of arraylist add() worst case. getHits() just use binarySearch(), so time = O(logn)

    public class HitCounter {
        ArrayList<Integer> record;
        /** Initialize your data structure here. */
        public HitCounter() {
            record = new ArrayList<Integer>();
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            record.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 len = record.size();
            int index = Collections.binarySearch(record, new Integer(timestamp));
            if (index >= 0) {
                while (index < len && record.get(index) == timestamp) {
                    index++;
                }
            }
            index = index < 0 ? -index-1 : index;
            if (timestamp > 300) {
                int indexLower = Collections.binarySearch(record, new Integer(timestamp - 300));
                if (indexLower >= 0) {
                    while (indexLower < len && record.get(indexLower) == timestamp-300) {
                        indexLower++;
                    }
                }
                indexLower = indexLower < 0 ? -indexLower-1 : indexLower;
                return index - indexLower;
            } else {
                return index;
            }
        }
    }

Log in to reply
 

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