点击上方蓝字关注力扣
下面开始今天的学习～
力扣 981. 基于时间的键值存储（点击查看题目）
题目描述
设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。
实现 TimeMap 类：
  • TimeMap() 初始化数据结构对象
  • void set(String key, String value, int timestamp) 存储键 key、值 value，以及给定的时间戳 timestamp。
  • String get(String key, int timestamp)
  • 返回先前调用 set(key, value, timestamp_prev) 所存储的值，其中 timestamp_prev <= timestamp 。
  • 如果有多个这样的值，则返回对应最大的  timestamp_prev 的那个值。
  • 如果没有值，则返回空字符串（""）。
示例 
输入：["TimeMap", "set", "get", "get", "set", "get", "get"][[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]输出：[null, null, "bar", "bar", null, "bar2", "bar2"]解释：TimeMap timeMap = new TimeMap();timeMap.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" ，时间戳 timestamp = 1   timeMap.get("foo", 1); // 返回 "bar"timeMap.get("foo", 3); // 返回 "bar", 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"） 。timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2" ，时间戳 timestamp = 4  timeMap.get("foo", 4); // 返回 "bar2"timeMap.get("foo", 5);         // 返回 "bar2"
提示：
  • 1 <= key.length, value.length <= 100
  • key 和 value 由小写英文字母和数字组成
  • 1 <= timestamp <= 10^7
  • set 操作中的时间戳 timestamp 都是严格递增的
  • 最多调用 set 和 get 操作 2 * 10^5 次

方法一：哈希表 + 二分查找

为实现 get 操作，我们需要用一个哈希表存储 set 操作传入的数据。具体地，哈希表的键为字符串 key，值为一个二元组列表，二元组中存储的是时间戳 timestamp 和值 value。
由于 set 操作中的时间戳都是严格递增的，因此二元组列表中保存的时间戳也是严格递增的，这样我们可以根据 get 操作中的 key 在哈希表中找到对应的二元组列表 pairs，然后根据 timestamp 在 pairs 中二分查找。我们需要找到最大的不超过timestamp 的时间戳，对此，我们可以二分找到第一个超过 timestamp 的二元组下标 i，若 i>0 则说明目标二元组存在，即 pairs[i−1]，否则二元组不存在，返回空字符串。
C++
classTimeMap {unordered_map<string, vector<pair<int, string>>> m;public: TimeMap() {}voidset(string key, string value, int timestamp){ m[key].emplace_back(timestamp, value); }stringget(string key, int timestamp){auto &pairs = m[key];// 使用一个大于所有 value 的字符串，以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置 pair<int, string> p = {timestamp, string({127})};auto i = upper_bound(pairs.begin(), pairs.end(), p);if (i != pairs.begin()) {return (i - 1)->second; }return""; }};
Java
classTimeMap {classPairimplementsComparable<Pair> {int timestamp; String value;publicPair(int timestamp, String value){this.timestamp = timestamp;this.value = value; }publicinthashCode(){return timestamp + value.hashCode(); }public boolean equals(Object obj){if (obj instanceof Pair) { Pair pair2 = (Pair) obj;returnthis.timestamp == pair2.timestamp && this.value.equals(pair2.value); }returnfalse; }publicintcompareTo(Pair pair2){if (this.timestamp != pair2.timestamp) {returnthis.timestamp - pair2.timestamp; } else {returnthis.value.compareTo(pair2.value); } } } Map<String, List<Pair>> map;publicTimeMap(){map = new HashMap<String, List<Pair>>(); }publicvoidset(String key, String value, int timestamp){ List<Pair> pairs = map.getOrDefault(key, new ArrayList<Pair>()); pairs.add(new Pair(timestamp, value));map.put(key, pairs); }public String get(String key, int timestamp){ List<Pair> pairs = map.getOrDefault(key, new ArrayList<Pair>());// 使用一个大于所有 value 的字符串，以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置 Pair pair = new Pair(timestamp, String.valueOf((char) 127));int i = binarySearch(pairs, pair);if (i > 0) {return pairs.get(i - 1).value; }return""; }privateintbinarySearch(List<Pair> pairs, Pair target){int low = 0, high = pairs.size() - 1;if (high < 0 || pairs.get(high).compareTo(target) <= 0) {return high + 1; }while (low < high) {int mid = (high - low) / 2 + low; Pair pair = pairs.get(mid);if (pair.compareTo(target) <= 0) { low = mid + 1; } else { high = mid; } }return low; }}
C#
publicclassTimeMap { Dictionary<string, IList<Tuple<int, string>>> dictionary;publicTimeMap() { dictionary = new Dictionary<string, IList<Tuple<int, string>>>(); }publicvoidSet(string key, stringvalue, int timestamp) {if (dictionary.ContainsKey(key)) { dictionary[key].Add(new Tuple<int, string>(timestamp, value)); } else { IList<Tuple<int, string>> tuples = new List<Tuple<int, string>>(); tuples.Add(new Tuple<int, string>(timestamp, value)); dictionary.Add(key, tuples); } }publicstringGet(string key, int timestamp) { IList<Tuple<int, string>> tuples = dictionary.ContainsKey(key) ? dictionary[key] : new List<Tuple<int, string>>();// 使用一个大于所有 value 的字符串，以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置 Tuple<int, string> tuple = new Tuple<int, string>(timestamp, ((char) 127).ToString());int i = BinarySearch(tuples, tuple);if (i > 0) {return tuples[i - 1].Item2; }return""; }privateintBinarySearch(IList<Tuple<int, string>> tuples, Tuple<int, string> target) {int low = 0, high = tuples.Count - 1;if (high < 0 || Compare(tuples[high], target) <= 0) {return high + 1; }while (low < high) {int mid = (high - low) / 2 + low; Tuple<int, string> tuple = tuples[mid];if (Compare(tuple, target) <= 0) { low = mid + 1; } else { high = mid; } }return low; }privateintCompare(Tuple<int, string> tuple1, Tuple<int, string> tuple2) {if (tuple1.Item1 != tuple2.Item1) {return tuple1.Item1 - tuple2.Item1; } else {returnstring.CompareOrdinal(tuple1.Item2, tuple2.Item2); } }}
Golang  
type pair struct { timestamp int value string}type TimeMap struct { m map[string][]pair}funcConstructor()TimeMap {return TimeMap{map[string][]pair{}}}func(m *TimeMap)Set(key string, value string, timestamp int) { m.m[key] = append(m.m[key], pair{timestamp, value})}func(m *TimeMap)Get(key string, timestamp int)string { pairs := m.m[key] i := sort.Search(len(pairs), func(i int)bool { return pairs[i].timestamp > timestamp })if i > 0 {return pairs[i-1].value }return""}
JavaScript
var TimeMap = function() {this.map = newMap();};TimeMap.prototype.set = function(key, value, timestamp) {if (this.map.has(key)) {this.map.get(key).push([value, timestamp]); } else {this.map.set(key, [[value, timestamp]]); }};TimeMap.prototype.get = function(key, timestamp) {let pairs = this.map.get(key)if (pairs) {let low = 0, high = pairs.length - 1;while (low <= high) {let mid = Math.floor((high - low) / 2) + low;if (pairs[mid][1] > timestamp) { high = mid - 1; } elseif (pairs[mid][1] < timestamp) { low = mid + 1; } else {return pairs[mid][0]; } }if (high >= 0) {return pairs[high][0]; }return""; }return"";};
复杂度分析
  • 时间复杂度：
  • 初始化 TimeMap 和 set 操作均为O(1)；
  • get 操作为 O(logn)，其中 n 是 set 操作的次数。最坏情况下 set 操作插入的 key 均相同，这种情况下 get 中二分查找的次数为 O(logn)。
  • 空间复杂度：O(n)，其中 n 是set 操作的次数。我们需要使用哈希表保存每一次 set 操作的信息。
BY / 
本文作者：力扣
编辑&版式：霍霍
声明：本文归“力扣”版权所有，如需转载请联系。
点个在看，少个 bug👇
继续阅读
阅读原文