Leetcode 981. Time Based Key-Value Store（二分查找）
题目来源：https://leetcode.com/problems/time-based-key-value-store/description/
标记难度：Medium
提交次数：1/1
代码效率：33.33%（212ms）
题意
给定一系列set和get操作，其中：
- 每个set操作包含一个key，一个value和一个timestamp，其中timestamp是严格递增的
- 每个get操作包含一个key和一个timestamp，要求找出与这个key相等且时间戳<=timestamp的set操作中时间戳最大的set对应的value
所有操作总数不超过12万次。
分析
这个题目咋一看很唬人，其实完全不是那么回事。解题思路很简单：
- 用一个map维护set操作的key对应的value和timestamp对的列表
- 对于每个get操作，从key对应的列表中通过二分查找，找到最大的符合要求的timestamp对应的value
如果map用的是Hash Table，记总操作次数为N，那么set的复杂度是O(1)，get的复杂度是O(log(N))；如果用的是树结构的话，那set的复杂度就是O(log(N))，get的复杂度是O(log^2(N))（不过显然可以把它写得更好一些）。
这次我写了二分查找。一般来说，如果二分查找（m = (l + r) / 2）之后的转移条件是l = m + 1，r = m的话，那循环条件就可以写成l < r；但是如果转移条件是l = m，r = m - 1的话，循环条件就需要写成l < r-1，然后判断l还是r是解……
代码
1234567891011121314151617181920212223242526272829 | 大专栏 Leetcode 981. Time Based Key-Value Store（二分查找）"class">class {private: map<string, vector<pair<int, string>>> mmap; public: TimeMap() { } void set(string key, string value, int timestamp) { mmap[key].emplace_back(timestamp, value); } string get(string key, int timestamp) { if (mmap.find(key) == mmap.end()) return ""; int n = mmap[key].size(); if (mmap[key][0].first > timestamp) return ""; int l = 0, r = n - 1; while (l < r - 1) { int m = (l + r) / 2; if (mmap[key][m].first <= timestamp) l = m; else r = m - 1; } if (mmap[key][r].first <= timestamp) return mmap[key][r].second; return mmap[key][l].second; }}; |
相关推荐
yaohustiAC 2020-06-11
Clairezz 2020-05-10
数据与算法之美 2020-06-28
faiculty 2020-08-20
wuxiaosi0 2020-06-28
freedomfanye 2020-06-28
只能做防骑 2020-06-01
computermaths 2020-05-09
dushine00 2020-04-27
Codeeror 2020-04-20
数据与算法之美 2020-04-15
katyusha 2020-04-15
lickylin 2020-02-29
chenfei0 2020-02-26
wulaxiaohei 2020-02-15
baike 2020-02-03
ustbfym 2020-02-02
Unimen 2020-01-11
yuanran0 2019-12-31