Leecode＜每日一题＞基于时间的键值存储

题目链接

思路：哈希表+二分查找

struct node
{
    string value;
    int time;

    node(string v,int t):value(v),time(t)
    {}
};


class TimeMap {
public:

    unordered_map<string, vector<node>> mp;
    /** Initialize your data structure here. */
    TimeMap() {
        
    }

    void set(string key, string value, int timestamp) {
        if (mp.count(key))
        {
            mp[key].push_back(node(value, timestamp));
        }
        else
        {
            vector<node> tab;
            tab.push_back(node(value, timestamp));
            mp[key] = tab;
        }
    }

    string get(string key, int timestamp) {
        if (!mp.count(key)) return "";
        vector<node>& tab = mp[key];
        int l = 0,r = tab.size();
        int m;

        while (l < r)
        {
            m = (l + r) / 2;
            if (timestamp == tab[m].time)
            {
                return tab[m].value;
            }
            else if (timestamp > tab[m].time)
            {
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }
        while (l>=0)
        {
            if (l<tab.size() && timestamp >= tab[l].time) return tab[l].value;
            l--;
        }
        return "";
    }
};