Leetcode 981. Time Based Key-Value Store

Tyan

发布于 2021-07-08 15:52:40

37200

代码可运行

文章被收录于专栏：SnailTyanSnailTyan

运行总次数：0

代码可运行

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

**解析：**采用了一个新的数据结构bisect来保证有序的二分查找和插入，采用双列表实现timestamp和value的有序字典。

Version 1

class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.timestamps = collections.defaultdict(list)
        self.values = collections.defaultdict(list)

        
    def set(self, key: str, value: str, timestamp: int) -> None:
        position = bisect.bisect(self.timestamps[key], timestamp)
        self.timestamps[key].insert(position, timestamp)
        self.values[key].insert(position, value)


    def get(self, key: str, timestamp: int) -> str:
        if key in self.timestamps:
            if timestamp < self.timestamps[key][0]:
                return ''
            elif timestamp > self.timestamps[key][-1]:
                return self.values[key][-1]
            else:
                position = bisect.bisect_right(self.timestamps[key], timestamp)
                return self.values[key][position - 1]
        else:
            return ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)