981. 基于时间的键值存储 力扣(中等) 又学到了map新用法,lower_bound()

题目描述: 

创建一个基于时间的键值存储类 TimeMap,它支持下面两个操作:

1. set(string key, string value, int timestamp)

存储键 key、值 value,以及给定的时间戳 timestamp。
2. get(string key, int timestamp)

返回先前调用 set(key, value, timestamp_prev) 所存储的值,其中 timestamp_prev <= timestamp。
如果有多个这样的值,则返回对应最大的  timestamp_prev 的那个值。
如果没有值,则返回空字符串("")。

示例 1:

输入:inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
输出:[null,null,"bar","bar",null,"bar2","bar2"]
解释: 
TimeMap kv;  
kv.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" 以及时间戳 timestamp = 1  
kv.get("foo", 1); // 输出 "bar"  
kv.get("foo", 3); // 输出 "bar" 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值,所以唯一的值位于时间戳 1 处(即 "bar")  
kv.set("foo", "bar2", 4);  
kv.get("foo", 4); // 输出 "bar2"  
kv.get("foo", 5); // 输出 "bar2"  

题源:https://leetcode-cn.com/problems/time-based-key-value-store/

学点:

1、for(auto i: map)  这种情况下,取值用   i.first  或   i.second

     但是,如果是map<,>::iterator i情况,应该用  i->first,  i->second

2、lower_bound,和upper_bound都是二分查找,效率高。

STL--map中的用法:std::map::lower_bound与td::map::upper_bound

iterator lower_bound( const key_type &key ): 返回一个迭代器,指向键值>= key的第一个元素。
iterator upper_bound( const key_type &key ):返回一个迭代器,指向键值> key的第一个元素。

lower_bound 返回值是一个指向容器中第一个元素的迭代器,该容器中的元素满足不在k的前面,(返回元素的键值>=k)

upper_bound返回值是一个指向容器中第一个元素的迭代器,该容器中的元素满足在k的后面,(返回元素的键值>k)

STL中的用法:std::lower_bound与std::upper_bound

ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)

返回一个非递减序列[first, last)中的第一个>= 值val的位置。

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)

返回一个非递减序列[first, last)中的第一个>值val的位置。

代码:

class TimeMap {
public:
    /** Initialize your data structure here. */
    map<string,map<int,string>> mp;
    TimeMap() {

    }
    
    void set(string key, string value, int timestamp) {
        mp[key][timestamp]=value;
        return;
    }
    
    string get(string key, int timestamp) {
        if (mp.find(key)==mp.end()) return "";   // 如果都不存在key
        if (mp[key].begin()->first>timestamp) return ""; //如果存在key,但是时间均大于timestamp,这里只能用  ->fisrt,.first会报错
        if (mp[key].find(timestamp)!=mp[key].end()) return mp[key][timestamp];  //  如果存在key,且,存在等于timestamp,直接返回即可
        /*string res="";   // 下面这段代码tle,需要二分查找
        int maxtime;
            for(auto j : mp[key])
                if (j.first<=timestamp)
                {
                    maxtime=j.first;
                    res=j.second;
                } else break;
        return res;*/
        map<int, string>::iterator ii=mp[key].upper_bound(timestamp);
        ii--;
        return ii->second;
    }
};

/**
 * 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);
 */

 

上一篇:力扣 981. 基于时间的键值存储


下一篇:力扣每日一题21.07.10