一、题目

创建一个基于时间的键值存储类 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）HashMap+TreeMap

善于使用数据结构可以快速解题，使用HashMap的特性，可以快速找到key对应的entry，由于要找到小于等于给定timestamp的value，使用TreeMap的特性可以快速找到

三、代码

1）HashMap+TreeMap

  1. class TimeMap {
  2.     private Map<String, TreeMap<Integer, String>> map;
  3.     public TimeMap() {
  4.         map = new HashMap<String, TreeMap<Integer, String>>();
  5.     }
  7.     public void set(String key, String value, int timestamp) {
  8.         // if (!map.containsKey(key)) {
  9.         //     map.put(key, new TreeMap<Integer, String>());
  10.         // }
  11.         // map.get(key).put(timestamp, value);    // 可化简为下面一行
  12.         map.computeIfAbsent(key, k -> new TreeMap<Integer, String>()).put(timestamp, value);
  13.     }
  15.     public String get(String key, int timestamp) {
  16.         if (!map.containsKey(key)) {
  17.             return "";
  18.         }
  19.         Map.Entry<Integer, String> entry = map.get(key).floorEntry(timestamp);
  20.         if (entry == null) {
  21.             return "";
  22.         }
  23.         return entry.getValue();
  24.     }

时间复杂度为O(nlogC)，C是单个key中不同值的数量，空间复杂度为O(n)