4ms C++ solution, O(300) time, O(300) space, no complicated data structure


  • 0
    T

    My basic idea is when there is a timestamp, I fix the current valid cycle [timestamp - 300, timestamp]. In order to achieve this, I record last timestamp of hit prev.

    • If prev is less than timestamp - 300, then obviously, nothing happened for last cycle
    • Otherwise, [pre + 1, timestamp] should be reset to 0

    For storage, I use vector to store 300 elements in a circular way. Since time starts at 1, so (time - 1) % 300 can get the right position.

    class HitCounter {
    public:
    /** Initialize your data structure here. */
    HitCounter() {
        m_vHits.assign(300, 0);
        m_iPrev = 0;
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        fix_cycle(timestamp);
        m_vHits[(timestamp - 1) % 300]++;
        m_iPrev = timestamp;
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        fix_cycle(timestamp);
        return accumulate(m_vHits.begin(), m_vHits.end(), 0);
    }
    private:
    vector<int> m_vHits;
    int m_iPrev;//last timestamp of hit
    
    void fix_cycle(int timestamp)
    {
        int start = timestamp - 300 + 1;//start of this valid cycle
        if(start > m_iPrev)//nothing happend for last cycle, reset all
        {
            m_vHits.clear();
            m_vHits.assign(300, 0);
        }
        else//[start--m_iPrev] should be kept, but nothing happened between [m_iPrev -- timestamp], reset as 0 
        {
            for(int i = m_iPrev + 1; i <= timestamp; ++i)
                m_vHits[(i - 1) % 300] = 0;
        }
    }
    

    };

    /**

    • Your HitCounter object will be instantiated and called as such:
    • HitCounter obj = new HitCounter();
    • obj.hit(timestamp);
    • int param_2 = obj.getHits(timestamp);
      */

  • 0
    I

    Hang on, so if the previous timestamp is less than timestamp - 300, that means that everything up to m_iPrev is old entry and should be removed from the array, right?


  • 0
    I

    If the previous time is within timestamp - 300 and timestamp, shouldn't the entries from timestamp - 300 to prev be kept, since they are within 5 minutes? You should only be clearing out the entries older than 5 minutes, right? This is very confusing..


Log in to reply
 

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