981.基于时间的键值存储

链接：981.基于时间的键值存储
难度：Medium
标签：设计、哈希表、字符串、二分查找
简介：创建一个基于时间的键值存储类 TimeMap。

题解 1 - typescript

• 编辑时间：2021-07-10
• 执行用时：412ms
• 内存消耗：77.1MB
• 编程语言：typescript
• 解法介绍：利用 map 储存所有值。

class TimeMap {
  private map: Record<string, [string, number][]> = {};
  set(key: string, value: string, timestamp: number): void {
    let list = this.map[key];
    if (!list) this.map[key] = list = [];
    list.push([value, timestamp]);
  }
  get(key: string, timestamp: number): string {
    return this.find(this.map[key] ?? [], timestamp);
  }
  private find(
    list: [string, number][],
    timestamp: number,
    first = 0,
    last = list.length - 1
  ): string {
    if (first > last) {
      while (first > list.length - 1) first--;
      while (first >= 0) {
        if (list[first][1] < timestamp) return list[first][0];
        first--;
      }
      return '';
    }
    const mid = (first + last) >> 1;
    const [midStr, midTime] = list[mid];
    if (midTime > timestamp) return this.find(list, timestamp, first, mid - 1);
    else if (midTime < timestamp) return this.find(list, timestamp, mid + 1, last);
    else return midStr;
  }
}

题解 2 - typescript

• 编辑时间：2021-08-14
• 执行用时：404ms
• 内存消耗：76.4MB
• 编程语言：typescript
• 解法介绍：map 储存，二分查找。

class TimeMap {
  map = new Map<string, [string, number][]>();
  set(key: string, value: string, timestamp: number): void {
    let data = this.map.get(key);
    if (!data) this.map.set(key, (data = []));
    data.push([value, timestamp]);
  }
  get(key: string, timestamp: number): string {
    let data = this.map.get(key);
    if (!data) return '';
    const idx = this.bs(data, timestamp);
    if (idx === 0) {
      if (data[idx][1] > timestamp) return '';
      else return data[idx][0];
    }
    if (data[idx][1] <= timestamp) return data[idx][0];
    return data[idx - 1][0];
  }
  bs(data: [string, number][], timestamp: number): number {
    let l = 0;
    let r = data.length - 1;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (data[mid][1] > timestamp) r = mid;
      else l = mid + 1;
    }
    return l;
  }
}