0981-基于时间的键值存储

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。

实现 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 <= 107
  • set 操作中的时间戳 timestamp 都是严格递增的
  • 最多调用 set 和 get 操作 2 * 105 次

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

为实现 get 操作，我们需要用一个哈希表存储 set 操作传入的数据。具体地，哈希表的键为字符串 key，值为一个二元组列表，二元组中存储的是时间戳 timestamp 和值 value。

由于 set 操作中的时间戳都是严格递增的，因此二元组列表中保存的时间戳也是严格递增的，这样我们可以根据 get 操作中的 key 在哈希表中找到对应的二元组列表 pairs，然后根据 timestamp 在 pairs 中二分查找。我们需要找到最大的不超过 timestamp 的时间戳，对此，我们可以二分找到第一个超过 timestamp 的二元组下标 i，若 i>0 则说明目标二元组存在，即 pairs}[i-1]，否则二元组不存在，返回空字符串。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TimeMap {
    unordered_map<string, vector<pair<int, string>>> m;

public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        m[key].emplace_back(timestamp, value);
    }

    string get(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 "";
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class TimeMap {
    class Pair implements Comparable<Pair> {
        int timestamp;
        String value;

        public Pair(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }

        public int hashCode() {
            return timestamp + value.hashCode();
        }

        public boolean equals(Object obj) {
            if (obj instanceof Pair) {
                Pair pair2 = (Pair) obj;
                return this.timestamp == pair2.timestamp && this.value.equals(pair2.value);
            }
            return false;
        }

        public int compareTo(Pair pair2) {
            if (this.timestamp != pair2.timestamp) {
                return this.timestamp - pair2.timestamp;
            } else {
                return this.value.compareTo(pair2.value);
            }
        }
    }

    Map<String, List<Pair>> map;

    public TimeMap() {
        map = new HashMap<String, List<Pair>>();
    }
    
    public void set(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 "";
    }

    private int binarySearch(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;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class TimeMap {
    Dictionary<string, IList<Tuple<int, string>>> dictionary;

    public TimeMap() {
        dictionary = new Dictionary<string, IList<Tuple<int, string>>>();
    }
    
    public void Set(string key, string value, 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);
        }
    }
    
    public string Get(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 "";
    }

    private int BinarySearch(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;
    }

    private int Compare(Tuple<int, string> tuple1, Tuple<int, string> tuple2) {
        if (tuple1.Item1 != tuple2.Item1) {
            return tuple1.Item1 - tuple2.Item1;
        } else {
            return string.CompareOrdinal(tuple1.Item2, tuple2.Item2);
        }
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
type pair struct {
    timestamp int
    value     string
}

type TimeMap struct {
    m map[string][]pair
}

func Constructor() 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 ""
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var TimeMap = function() {
    this.map = new Map();
};

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;
            } else if (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(\log n)，其中 n 是 set 操作的次数。最坏情况下 set 操作插入的 key 均相同，这种情况下 get 中二分查找的次数为 O(\log n)。

  • 空间复杂度：O(n)，其中 n 是 set 操作的次数。我们需要使用哈希表保存每一次set 操作的信息。

 Comments
On this page
0981-基于时间的键值存储