【红黑树】981. 基于时间的键值存储（中等）
让我们看看这道题目的描述
这道题目属于设计类题目，我们要想一个合适的数据结构，用来保存变量。
我们可以用哈希表来实现，key为需要存储的键，value需要保存两个变量，一个为对应的值，另一个为时间戳，因为value在存储的时候，需要按时间戳来排序，故我们可以设计成红黑树
红黑树内部可以默认实现排序或者自定义排序，为我们省去了一些排序的操作
class TimeMap {private Map<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> temp = map.getOrDefault(key, new TreeMap<>());temp.put(timestamp, value);map.put(key, temp);}public String get(String key, int timestamp) {if(!map.containsKey(key)) return "";TreeMap<Integer, String> temp = map.get(key);if(temp.containsKey(timestamp)) return temp.get(timestamp);if(temp.floorKey(timestamp) != null) return temp.get(temp.floorKey(timestamp));return "";}}
这道题目的做法并不惟一，我们也可以用数组来保存对应的值，把数组的索引看作时间戳就可以。也可以自己实现一个内部类来实现。
class TimeMap {private Map<String, String[]> map;public TimeMap() {map = new HashMap();}public void set(String key, String value, int timestamp) {if(!map.containsKey(key)){String [] innerMap = new String[125000];innerMap[timestamp] = value;map.put(key, innerMap);}else{map.get(key)[timestamp] = value;}}public String get(String key, int timestamp) {if(!map.containsKey(key)){return "";}else{String[] tempMap = map.get(key);for(int i = timestamp - 1; i >= 0; i--){if(null != tempMap[i+1]) return tempMap[i+1];}return "";}}}