英雄算法6月9号

class TimeMap {
    unordered_map >> table;
public:
    TimeMap() {}
    
    void set(string key, string value, int timestamp) {
        table[key].emplace_back(timestamp, value);//使用emplace_back相比于push_back更快  (1)
    }
    
    string get(string key, int timestamp) {
        auto& cp = table[key];//一定要用引用，可以大幅度减少拷贝时间		(2)

        int l = 0, len = cp.size();
        int r = len-1, ans = len;
        while(l <= r){//二分查找
            int mid = (l+r)/2;
            if(cp[mid].first <= timestamp){//中间的小
                ans = mid;//可行解
                l = mid+1;
            }
            else{
                r = mid-1;
            }
        }
        if(ans == len){//ans没有修改过
            return "";
        }
        return cp[ans].second;
    }
};

思路

本题做题思路相对清晰，恶心的是使用怎样的自定义数据结构存储数据。

本题key可以对应多个value对（一个是string，另一个是int）。而value又可以分为两大类。1.string value，2.int timestamp。

既然是键值对，那么第一个选择就是unorded_map。不过unorded_map的value需要是自定义类型，因为对应多对value。

在这里，我们选择pair，pair其实就是结构体，其好处就是选择其两个元素十分方便。但是，pair不具有扩展功能，不能实现一个key对应多个value对，所以我们需要用vector包装。

数据对象的存储使用

unordered_map >> table;
//table的key类型是string,对应的value是 vector>
//vector中存储着不同的int,string对，他们都用pair存储

//往table中存储数据

table[key] //返回vector的对象
table[key].emplace_back() //vector自带的方法
table[key].emplace_back(timestamp, value) //赋值pair

（1）这里使用emplace_back的原因是，相较于push_back，更加高效

• emplace_back() 函数在原理上比 push_back() 有了一定的改进，包括在内存优化方面和运行效率方面。内存优化主要体现在使用了就地构造（直接在容器内构造对象，不用拷贝一个复制品再使用）+强制类型转换的方法来实现，在运行效率方面，由于省去了拷贝构造过程，因此也有一定的提升。

数据对象的查找

首先就是依据key进行查找，这可以交个unordered_map解决。我们需要处理的对象是它返回的vector对象，这里我们必须要使用引用接受这个对象，（1）

引用无需调用拷贝函数，因此大大减少程序运行时间。

class Solution {
public:
    #define ll long long
    int findNthDigit(int n) {
        if(n<9){return n;}
        ll floor = 0, curNumLen = 0;
        for(floor = 0; curNumLen < n; ++floor){//确定n在第几层
            curNumLen += 9*(floor+1)*pow(10,floor);
        }
        --floor;//减去最后依次多余的循环判断
        curNumLen -= 9*(floor+1)*pow(10,floor);

        int left = (n-curNumLen)%(floor+1);//在第numth个数字中的余数
        if(left > 0){left = 1;}//如果大于0，则表示在下一个数字上，否则刚好在数字末尾
        
        ll numth = (n-curNumLen)/(floor+1)+left;//第numth个数字
        ll index = (n-curNumLen)-(numth-1)*(floor+1)-1;//在第numth个数字的下标index
        ll num = pow(10,floor)+numth-1;

        return to_string(num)[index]-'0';
    }
};