★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：为敢（WeiGanTechnologies）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10311344.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Create a timebased key-value store class TimeMap, that supports two operations.

1. set(string key, string value, int timestamp)

• Stores the key and value, along with the given timestamp.

2. get(string key, int timestamp)

• Returns a value such that set(key, value, timestamp_prev)was called previously, with timestamp_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 (""). 

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"   

Input: inputs =  

Note:

1. All key/value strings are lowercase.
2. All key/value strings have length in the range [1, 100]
3. The timestamps for all TimeMap.set operations are strictly increasing.
4. 1 <= timestamp <= 10^7
5. TimeMap.set and TimeMap.get functions will be called a total of 120000 times (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. 所有的键/值字符串都是小写的。
2. 所有的键/值字符串长度都在 [1, 100] 范围内。
3. 所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。
4. 1 <= timestamp <= 10^7
5. TimeMap.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  */