981. Time Based Key-Value Store
Tags:
Medium
Skills:
Binary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bạn cần thiết kế một cấu trúc dữ liệu cho phép lưu trữ nhiều giá trị cho cùng một key tại các thời điểm cụ thể khác nhau, và truy xuất giá trị của key tại một thời điểm nhất định
Approach
Set
{"foo": [(1, "bar"), (4, "bar2")]}.set, bạn chỉ cần thêm (append) vào cuối danh sách vì đề bài đảm bảo các timestamp luôn tăng dầnGet
get(key, timestamp), bạn cần tìm giá trị có timestamp lớn nhất nhưng không vượt quá timestamp được hỏi.Solution
1class TimeMap {
2 store: Record<string, {timestamp: number, value: string}[]>;
3 constructor() {
4 this.store = {};
5 }
6
7 set(key: string, value: string, timestamp: number): void {
8 if(!this.store[key]) {
9 this.store[key] = [];
10 }
11 this.store[key].push({timestamp, value});
12 }
13
14 get(key: string, timestamp: number): string {
15 if(!this.store[key]) return "";
16 const arr = this.store[key];
17 let left = 0;
18 let right = arr.length - 1;
19 let res = "";
20
21 while(left <= right) {
22 const mid = left + Math.floor((right - left) / 2);
23 if(arr[mid].timestamp === timestamp) {
24 return arr[mid].value;
25 }
26
27 if(arr[mid].timestamp < timestamp) {
28 res = arr[mid].value;
29 left = mid + 1;
30 } else {
31 right = mid - 1;
32 }
33 }
34
35 return res;
36 }
37}
38
39/**
40 * Your TimeMap object will be instantiated and called as such:
41 * var obj = new TimeMap()
42 * obj.set(key,value,timestamp)
43 * var param_2 = obj.get(key,timestamp)
44 */