[Swift]LeetCode981. 基于时间的键值存储 | Time Based Key-Value Store
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：为敢（WeiGanTechnologies）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10311344.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Create a timebased key-value store class TimeMap, that supports two operations.
1. set(string key, string value, int timestamp)
- Stores the
keyandvalue, along with the giventimestamp.
2. get(string key, int timestamp)
- Returns a value such that
set(key, value, timestamp_prev)was called previously, withtimestamp_prev <= timestamp. - If there are multiple such values, it returns the one with the largest
timestamp_prev. - If there are no values, it returns the empty string (
"").
Example 1:
Input: inputs =
TimeMap kv;
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1
kv.get("foo", 1); // output "bar"
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"
kv.set("foo", "bar2", 4);
kv.get("foo", 4); // output "bar2"
kv.get("foo", 5); //output "bar2"
Example 2:
Input: inputs =
Note:
- All key/value strings are lowercase.
- All key/value strings have length in the range
[1, 100] - The
timestampsfor allTimeMap.setoperations are strictly increasing. 1 <= timestamp <= 10^7TimeMap.setandTimeMap.getfunctions will be called a total of120000times (combined) per test case.
创建一个基于时间的键值存储类 TimeMap，它支持下面两个操作：
1. set(string key, string value, int timestamp)
- 存储键
key、值value，以及给定的时间戳timestamp。
2. get(string key, int timestamp)
- 返回先前调用
set(key, value, timestamp_prev)所存储的值，其中timestamp_prev <= timestamp。 - 如果有多个这样的值，则返回对应最大的
timestamp_prev的那个值。 - 如果没有值，则返回空字符串（
""）。
示例 1：
输入：inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
输出：[null,null,"bar","bar",null,"bar2","bar2"]
解释：
TimeMap kv;
kv.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" 以及时间戳 timestamp = 1
kv.get("foo", 1); // 输出 "bar"
kv.get("foo", 3); // 输出 "bar" 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"）
kv.set("foo", "bar2", 4);
kv.get("foo", 4); // 输出 "bar2"
kv.get("foo", 5); // 输出 "bar2"
示例 2：
输入：inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]] 输出：[null,null,null,"","high","high","low","low"]
提示：
- 所有的键/值字符串都是小写的。
- 所有的键/值字符串长度都在
[1, 100]范围内。 - 所有
TimeMap.set操作中的时间戳timestamps都是严格递增的。 1 <= timestamp <= 10^7TimeMap.set和TimeMap.get函数在每个测试用例中将（组合）调用总计120000次。
2180 ms
1 class TimeMap {
2 var d:[Data]
3 var idx:[String:Int]
4
5 /** Initialize your data structure here. */
6 init() {
7 d = [Data]()
8 idx = [String:Int]()
9 }
10
11 func set(_ key: String, _ value: String, _ timestamp: Int) {
12 var lt = gets(key, timestamp)
13 var dd:Data = Data(value, lt, timestamp)
14 idx[key] = d.count
15 d.append(dd)
16 }
17
18 func get(_ key: String, _ timestamp: Int) -> String {
19 var i:Int = gets(key, timestamp)
20 if i == -1
21 {
22 return String()
23 }
24 else
25 {
26 return d[i].value
27 }
28 }
29
30 func gets(_ key: String, _ ts: Int) -> Int {
31 if idx[key] == nil
32 {
33 return -1
34 }
35 var p:Int = idx[key]!
36 while(p != -1 && d[p].ts > ts)
37 {
38 p = d[p].last
39 }
40 return p
41 }
42 }
43
44 struct Data
45 {
46 var value:String = String()
47 var last:Int = 0
48 var ts:Int = 0
49
50 init()
51 {
52
53 }
54
55 init(_ value:String,_ last:Int,_ ts:Int)
56 {
57 self.value = value
58 self.last = last
59 self.ts = ts
60 }
61 }
62
63 /**
64 * Your TimeMap object will be instantiated and called as such:
65 * let obj = TimeMap()
66 * obj.set(key, value, timestamp)
67 * let ret_2: String = obj.get(key, timestamp)
68 */