C++ better-than-O(n)-retrieve solution


  • 0
    M
    class LogSystem {
    public:
        LogSystem() {}
        
        void put(int id, string timestamp) {
            mp[timestamp] = id;
        }
        
        vector<int> retrieve(string s, string e, string gra) {
            vector<int> res;
            int len = prefix_len[gra];
            
            string pre_s = s.substr(0, len), pre_e = e.substr(0, len), upper = pre_e;
            ++upper.back();
            auto begin = mp.lower_bound(pre_s), end = mp.upper_bound(upper);
    
            for(auto it = begin; it != end; ++it){
                string tmp = (*it).first.substr(0, len);
                if(tmp >= pre_s && tmp <= pre_e)
                    res.push_back((*it).second);
            }
            return res;
        }
        
    private:
        unordered_map<string, int> prefix_len = {{"Year", 4}, {"Month", 7}, {"Day", 10}, {"Hour", 13}, {"Minute", 16}, {"Second", 19}};
        map<string, int> mp;
    };
    

Log in to reply
 

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