leetcode981

桃扇骨 2021-12-19 04:09 138阅读 0赞

考虑线性的搜索会超时，所以用二叉搜索来解决，代码如下：

1 class TimeMap:
     2     def __init__(self):
     3         self.ST = dict()
     4 
     5     def set(self, key: 'str', value: 'str', timestamp: 'int') -> 'None':
     6         if key in self.ST.keys():
     7             D = self.ST[key]#dict
     8             D.update({timestamp:value})
     9             self.ST.update({key:D})
    10         else:
    11             D = dict()
    12             D.update({timestamp:value})
    13             self.ST.update({key:D})
    14 
    15 
    16     def get(self, key: 'str', timestamp: 'int') -> 'str':
    17         if key in self.ST.keys():
    18             D = self.ST[key]
    19             V = self.binSearch(timestamp,D)
    20             return V
    21         else:
    22             return ''
    23 
    24     def binSearch(self,target,D):
    25         times = list(D.keys())
    26         n = len(times)
    27         minval = times[0]
    28         maxval = times[-1]
    29         if target < minval:
    30             return ''
    31 
    32         if target ==  minval:
    33             return D[times[0]]
    34 
    35         if target >= maxval:
    36             return D[times[-1]]
    37 
    38         left = 0
    39         right =  n - 1
    40         while left < right:
    41             mid = (left + right) // 2
    42             if times[mid] == target:
    43                 return D[times[mid]]
    44             elif times[mid]<target:
    45                 left = mid + 1
    46             elif times[mid]>target:
    47                 right = mid - 1
    48         if left == 0:
    49             return D[times[left]]
    50         else:
    51             return D[times[left-1]]

但是这种写法会超时，这应该是代码质量问题，目前没明白是啥原因。

哪位博友知道我的代码的问题，欢迎告知。

参考了一下别人的方案，看到一个线性搜索的解决方案，却可以通过。

1 class TimeMap:
     2 
     3     def __init__(self):
     4         """
     5         Initialize your data structure here.
     6         """
     7         self.dic = {}
     8 
     9     def set(self, key: 'str', value: 'str', timestamp: 'int') -> 'None':
    10         if key in self.dic:
    11             self.dic[key].append({
        'v': value, 't': timestamp})
    12         else:
    13             self.dic[key] = [{
        'v': value, 't': timestamp}]
    14 
    15     def get(self, key: 'str', timestamp: 'int') -> 'str':
    16         if key in self.dic:
    17             for kv in reversed(self.dic[key]):
    18                 if timestamp >= kv['t']:
    19                     return kv['v']
    20             return ""
    21         else:
    22             return ""

转载于:https://www.cnblogs.com/asenyang/p/10755690.html