[LeetCode] 981. Time Based Key-Value Store

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

  • TimeMap() Initializes the object of the data structure.
  • void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
  • String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.

Example 1:
Input
[“TimeMap”, “set”, “get”, “get”, “set”, “get”, “get”]
[[], [“foo”, “bar”, 1], [“foo”, 1], [“foo”, 3], [“foo”, “bar2”, 4], [“foo”, 4], [“foo”, 5]]
Output
[null, null, “bar”, “bar”, null, “bar2”, “bar2”]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set(“foo”, “bar”, 1); // store the key “foo” and value “bar” along with timestamp = 1.
timeMap.get(“foo”, 1); // return “bar”
timeMap.get(“foo”, 3); // return “bar”, since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is “bar”.
timeMap.set(“foo”, “bar2”, 4); // store the key “foo” and value “bar2” along with timestamp = 4.
timeMap.get(“foo”, 4); // return “bar2”
timeMap.get(“foo”, 5); // return “bar2”

Constraints:
1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits.
1 <= timestamp <= 107
All the timestamps timestamp of set are strictly increasing.
At most 2 * 105 calls will be made to set and get.

基于时间的键值存储。

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

实现 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 的那个值。
如果没有值，则返回空字符串（””）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/time-based-key-value-store
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - treemap

这个题有两种思路，一是用Java的 treemap，另一种是用到 binary search。

首先第一种思路，用 treemap。因为会存在多个键值是同样的 key，但是有不同的 value 和不同的 timestamp，所以一开始比较直观的思路一定是 hashmap<String, timestamp>，因为 hashmap 才能存储类似这种<key, value>键值对的数据。其次，题目要求当找到同样的 key，同样的 value 的时候，要返回最接近 timestamp 的 value，所以想到用 treemap<timestamp, String>，因为 treemap 是可以自动根据 key 排序的。

复杂度

  • treemap
    • 构造 treemap 的时间O(nlogn) - 每放进去一个元素就要重新排序一次
    • 空间O(n)

代码

treemap实现

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
class TimeMap {
	private HashMap<String, TreeMap<Integer, String>> map;

	/** Initialize your data structure here. */
	public TimeMap() {
		map = new HashMap<>();
	}

	public void set(String key, String value, int timestamp) {
		TreeMap<Integer, String> tmap = map.get(key);
		if (tmap == null) {
			tmap = new TreeMap<>();
			map.put(key, tmap);
		}
		tmap.put(timestamp, value);
	}

	public String get(String key, int timestamp) {
		TreeMap<Integer, String> tmap = map.get(key);
		if (tmap == null) {
			return "";
		}
		Integer floorKey = tmap.floorKey(timestamp);
		if (floorKey == null) {
			return "";
		}
		return tmap.get(floorKey);
	}
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

思路二 - 二分法

第二种思路是用到二分法。在不用 treemap 的前提下，我们依然需要 hashmap 存储 key 和 value（这里会是一个 list）的键值对，但是对于 value 相同但是 timestamp 不同的数据，我们可以自己创建一个类，把这个类放入 list，这样当 get key 的时候，实际上我们 get 到的是一个由 arraylist 串联好的，有相同 key 的 values。当你能得到这个 list 之后，可以根据给出的变量 timestamp 找到 list 中最接近于这个 timestamp 的键值对。因为题目给的时间戳一定是有序的所以这里我们无需再排序了。

复杂度

  • binary search
    • 时间O(logn)
    • 空间O(n)

代码

binary search实现

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
class Data {
    String val;
    int time;
    
    public Data(String val, int time) {
        this.val = val;
        this.time = time;
    }
}

class TimeMap {
    HashMap<String, List<Data>> map;

    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(new Data(value, timestamp));
    }
    
    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }
        return helper(map.get(key), timestamp);
    }

    private String helper(List<Data> list, int timestamp) {
        int left = 0;
        int right = list.size() - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid).time == timestamp) {
                return list.get(mid).val;
            } else if (list.get(mid).time < timestamp) {
                left = mid;
            } else if (list.get(mid).time > timestamp) {
                right = mid;
            }
        }
		// 因为如果right <= timestamp，那么right一定是更接近timestamp的时间
        if (list.get(right).time <= timestamp) {
            return list.get(right).val;
        }
        if (list.get(left).time <= timestamp) {
            return list.get(left).val;
        }
        return "";
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

相关题目

1
2
981. Time Based Key-Value Store
2034. Stock Price Fluctuation
#leetcode #hashmap #java #treemap #string #binary search #design
[LeetCode] 981. Time Based Key-Value Store
https://shurui91.github.io/posts/3002885147.html
Author
Aaron Liu
Posted on
May 16, 2020
Licensed under