Leetcode 981. 基于时间的键值存储（DAY 182）---- 二分查找学习期

痛定思痛。 2022-08-28 10:47 134阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解） ##

--------------------

class TimeMap { 
    public:
        unordered_map<string,vector<pair<int,string>>> map{ };
        TimeMap() { }
        int my_upper_bound(vector<pair<int,string>>& v,int target)
        { 
            int left = 0,right = v.size();
            while(left < right)
            { 
                int mid = (left + (right - left)/2);
                if(v[mid].first <= target)    left = mid+1;
                else    right = mid;
            }
            return left;
        }
    
        void set(string key, string value, int timestamp) { 
            map[key].emplace_back(timestamp,value);
        }
        
        string get(string key, int timestamp) { 
            string ret;
            if(map[key].empty()) return ret;
            int pos = my_upper_bound(map[key],timestamp) - 1;
            if(pos >=0 ) ret = map[key][pos].second;
            return ret;
        }
    };
    
    /** * Your TimeMap object will be instantiated and called as such: * TimeMap* obj = new TimeMap(); * obj->set(key,value,timestamp); * string param_2 = obj->get(key,timestamp); */

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/bff102ed78f04e27a44a8165937f0e43.png