（语法笔记 分析题解语法 二分 “unordered_map与vector＜pair＜＞＞“ 快速数组）leetocde 1146

*注：代码和题解思路来源于灵茶山艾府，因为我之前未接触过vector>与map的联合使用才写的笔记  链接：灵茶山艾府题解

核心思路：建立 unordered_map>> history;  令key为下标 vector存放不同快照引索的值，详看下文的输出

 unordered_map>> history; 

键：int 

值：vector>

history[0] 会访问 history 中键为 0 所对应的 std::vector>。如果该键不存在，会自动创建一个空的 vector。

// 正确访问方式
    if (!history[0].empty()) {
        int firstValue = history[0][0].first;  10
        int secondValue = history[0][0].second;  20
}

在代码里，使用 history[0].emplace_back(10, 20); 向 history 中键为 0 对应的 vector 里”插入”了一个 std::pair 对象，其值为 (10, 20)。

emplace_back(10, 20) 会在这个 vector 的末尾直接构造一个 std::pair 对象，这个对象的第一个元素是 10，第二个元素是 20。

  history[0].emplace_back(10, 20);
    history[0].emplace_back(30, 40);
    history[1].emplace_back(50, 60);

unordered_map数组的状态

key=index是下标题目说的下标
Key: 0
  (10, 20)history[key][0]  history[index][0].first –10快照索引  history[index][0].second–20
  (30, 40)history[key][0]
Key: 1
  (50, 60)

代码分析：

 int j = ranges::lower_bound(h, pair(snap_id + 1, 0)) – h.begin() – 1;
                中 pair(snap_id + 1, 0)
        假设 h 中有如下元素：
std::vector> h = { {10, 20}, {30, 40}, {50, 60} };

若 snap_id 为 20，那么 std::pair(snap_id + 1, 0) 就是 std::pair(21, 0)。
std::ranges::lower_bound 算法会依据 std::pair 的第一个元素进行比较，找到第一个大于等于 21 的元素，也就是 (30, 40)。
在这个过程中，std::pair 的第二个元素 0 并不影响查找结果，它只是占位，保证 std::pair 类型的完整性。

class SnapshotArray {
   unordered_map>> history; 
    int c_snap_id=0;
public:
    SnapshotArray(int length) {
    }
    
    void set(int index, int val) {
        history[index].emplace_back(c_snap_id,val);
    }
    
    int snap() {
        return c_snap_id++;
    }
    
    int get(int index, int snap_id) {
        auto &h=history[index];
        int j=ranges::lower_bound(h,pair(snap_id+1,0))-h.begin()-1;
        return j>=0?h[j].second:0;
    }
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

文章来源于互联网:（语法笔记 分析题解语法 二分 “unordered_map与vector＜pair＜＞＞“ 快速数组）leetocde 1146

相关推荐: 无聊的我对文心一言进行了灵魂拷问~

对比项 文心一言 ChatGPT 模型架构 可能基于不同的模型（如Transformer等） 基于GPT架构 训练数据 可能使用特定领域或任务的数据 可能使用广泛的互联网文本数据 知识面 可能在某些专业领域有优势 可能在社交、娱乐等领域有更强文本生成能力 应用…