981. Time Based Key-Value Store
Last updated
Was this helpful?
Last updated
Was this helpful?
Store "key, timestamp, value" as HashMap<String, ArrayList<Pair<Integer, String>>>. Call Collections.binarySearch( ) to support get operation
Time complexity of set operation
is and get operation
is
存储为 HashMap<String, ArrayList<Pair<Integer, String>>> 的数据结构,对应为 key: (timestamp, value)。 调用 Collections.binarySearch( ) 完成 get 操作。set 时间复杂度是O(1),get 时间复杂度为 O(lg N)。
Store "key, timestamp, value" as HashMap<String, TreeMap<Integer, String>>.
Time complexity of set operation
is and get operation
is
存储为 HashMap<String, TreeMap<Integer, String>> 的数据结构,对应为 key: (timestamp: value)。set 和 get 的时间复杂度都是 O(lg N)。
List is an interface. ArrayList, LinkedList, Stack and Vector are its implementation. ArrayList and LinkedList are the most common used. ArrayList accesses element quickly but add and delete element slowly. LinkedList accesses element slowly but add and delete element quickly.
Collections.binarySearch(List, key).
Search an element in a sorted List sorted in ascending order by binary search. If key exists, return its index. If key doesn't exist, return (-(insertion point)-1)
. If search an element in a decending sorted List, we can use collections.binarySearch(List, Key, collections.reverseOrder()).