Leetcode - Perform String Shifts
Leetcode - Design A Leaderboard

Leetcode - Time Based Key-Value Store

violet posted @ 5 年前 in 算法 with tags Algorithm Golang array BinarySearch , 443 阅读

https://leetcode.com/problems/time-based-key-value-store/

Create a timebased key-value store class TimeMap, that supports two operations.

1. set(string key, string value, int timestamp)

  • Stores the key and value, along with the given timestamp.

2. get(string key, int timestamp)

  • Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
  • If there are multiple such values, it returns the one with the largest timestamp_prev.
  • If there are no values, it returns the empty string ("").

 

Example 1:

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:   
TimeMap kv;   
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1   
kv.get("foo", 1);  // output "bar"   
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"   
kv.set("foo", "bar2", 4);   
kv.get("foo", 4); // output "bar2"   
kv.get("foo", 5); //output "bar2"  

 

1. Create two hashes. One is storing key -> [value1, value2, value3...], another is storing key -> [timestamp1, timestamp2, timestamp3...]

2. When getting the value by key, firstly find the [value1, value2, value3] and then run a binary search in [timestamp1, timestamp2, timestamp3] to find the index

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
type TimeMap struct {
    hash map[string][]string
    timestamp map[string][]int
}
 
 
/** Initialize your data structure here. */
func Constructor() TimeMap {
    return TimeMap{
        hash: map[string][]string{},
        timestamp: map[string][]int{},
    }
}
 
 
func (this *TimeMap) Set(key string, value string, timestamp int)  {
    this.hash[key] = append(this.hash[key], value)
    this.timestamp[key] = append(this.timestamp[key], timestamp)
}
 
 
func (this *TimeMap) Get(key string, timestamp int) string {
    if len(this.hash[key]) == 0 {
        return ""
    }
    index := find(this.timestamp[key], timestamp)
    if index < 0 {
        return ""
    }
    return this.hash[key][index]
}
 
func find(arr []int, timestamp int) int {
    l := 0
    r := len(arr)-1
    var mid int
    for l <= r {
        mid = (l + r) / 2
        if arr[mid] == timestamp {
            return mid
        }
        if arr[mid] > timestamp {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
     
    return r
}
 
 
/**
 * Your TimeMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Set(key,value,timestamp);
 * param_2 := obj.Get(key,timestamp);
 */
Small_feed 评论 (1)
1
[回复]
Smith 说:
12 个月前

The TimeMap class facilitates storing key-value pairs with associated timestamps and retrieving values based on timestamps. It supports set() to store values with timestamps and get() to retrieve the most recent value for a given key at a specified timestamp.. Lake Norman Real Estate

 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter