题目

题目来源：力扣（LeetCode）

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

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

示例：

  1. 输入：
  2. ["TimeMap", "set", "get", "get", "set", "get", "get"]
  3. [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
  4. 输出：
  5. [null, null, "bar", "bar", null, "bar2", "bar2"]
  7. 解释：
  8. TimeMap timeMap = new TimeMap();
  9. timeMap.set("foo", "bar", 1);  // 存储键 "foo" 和值 "bar" ，时间戳 timestamp = 1   
  10. timeMap.get("foo", 1);         // 返回 "bar"
  11. timeMap.get("foo", 3);         // 返回 "bar", 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"） 。
  12. timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2" ，时间戳 timestamp = 4  
  13. timeMap.get("foo", 4);         // 返回 "bar2"
  14. timeMap.get("foo", 5);         // 返回 "bar2"

思路分析

set 操作：
使用一个哈希表存储 set 操作传入的数据，其中哈希表的键为字符串 key，值为一个二维数组，二维数组中存储的是时间戳 timestamp 和 值 value。

get 操作：
由于 set 操作中的时间戳都是严格递增的，因此二维数组中保存的时间戳也是严格递增的。这样我们就可以根据 get 操作中的 key 在哈希表中找到对应的二维数组 pairs ，然后根据时间戳 timestamp 在 pairs 中二分查找。

我们需要找到最大的不超过 timestamp 的时间戳，对此，我们可以通过二分找到第一个超过 timestamp 的二元组下标 i，若 i > 0 则说明目标二元组存在，即 pairs[i - 1]，否则二元组不存在，返回空字符串。

  1. /**
  2. * Initialize your data structure here.
  3. */
  4. var TimeMap = function () {
  5.   this.map = new Map();
  6. };
  7. /**
  8. * @param {string} key
  9. * @param {string} value
  10. * @param {number} timestamp
  11. * @return {void}
  12. */
  13. TimeMap.prototype.set = function (key, value, timestamp) {
  14.   this.map.has(key) ? this.map.get(key).push([value, timestamp]) : this.map.set(key, [[value, timestamp]]);
  15. };
  16. /**
  17. * @param {string} key
  18. * @param {number} timestamp
  19. * @return {string}
  20. */
  21. TimeMap.prototype.get = function (key, timestamp) {
  23.   let pairs = this.map.get(key)
  24.   if (pairs) {
  25.     let left = 0, right = pairs.length - 1;
  26.     while (left <= right) {
  27.       // 二分
  28.       // mid = left + right >> 1;
  29.       let mid = Math.floor((right - left) / 2) + left;
  31.       if (pairs[mid][1] > timestamp) {
  32.         right = mid - 1;
  33.       } else if (pairs[mid][1] < timestamp) {
  34.         left = mid + 1;
  35.       } else {
  36.         return pairs[mid][0];
  37.       }
  38.     }
  39.     // 若 right >= 0 则说明目标二元组存在，即 pairs[i - 1]，否则二元组不存在，返回空字符串。
  40.     return right >= 0 ? pairs[right][0] : ''
  42.   }
  43.   return "";
  44. };
  45.   /**
  46. * Your TimeMap object will be instantiated and called as such:
  47. * var obj = new TimeMap()
  48. * obj.set(key,value,timestamp)
  49. * var param_2 = obj.get(key,timestamp)
  50. */