难度: Medium
Submission
运行时间: 44 ms
内存: 16.7 MB
class LogSystem:
def __init__(self):
self.time=dict()
self.t={"Year":3,"Month":6, "Day":9, "Hour":12, "Minute":15, "Second":18}
def put(self, id: int, timestamp: str) -> None:
self.time[timestamp]=id
def retrieve(self, start: str, end: str, granularity: str) -> List[int]:
ans=[]
gap=self.t[granularity]
s,e=start[:gap+1],end[:gap+1]
for k,v in self.time.items():
cur=k[:gap+1]
if s<=cur<=e:
ans.append(v)
return ans
# Your LogSystem object will be instantiated and called as such:
# obj = LogSystem()
# obj.put(id,timestamp)
# param_2 = obj.retrieve(start,end,granularity)
Explain
这个题解使用了哈希表来存储日志的时间戳和对应的 ID。在插入日志时，直接将时间戳作为键，ID 作为值存入哈希表。在检索日志时，根据给定的时间范围和粒度，遍历哈希表中的所有键值对，将时间戳截取到对应粒度，如果在给定的时间范围内，就将对应的 ID 加入结果列表。
时间复杂度: O(n)
空间复杂度: O(n)
class LogSystem:
def __init__(self):
self.time = dict() # 存储日志的哈希表
self.t = {"Year": 3, "Month": 6, "Day": 9, "Hour": 12, "Minute": 15, "Second": 18} # 不同粒度对应的时间戳长度
def put(self, id: int, timestamp: str) -> None:
self.time[timestamp] = id # 将时间戳作为键，ID 作为值存入哈希表
def retrieve(self, start: str, end: str, granularity: str) -> List[int]:
ans = [] # 存储结果的列表
gap = self.t[granularity] # 根据粒度获取时间戳的截取长度
s, e = start[:gap+1], end[:gap+1] # 截取起始和结束时间戳到对应粒度
for k, v in self.time.items(): # 遍历哈希表中的所有键值对
cur = k[:gap+1] # 将当前时间戳截取到对应粒度
if s <= cur <= e: # 如果当前时间戳在给定的时间范围内
ans.append(v) # 将对应的 ID 加入结果列表
return ans # 返回结果列表
# Your LogSystem object will be instantiated and called as such:
# obj = LogSystem()
# obj.put(id,timestamp)
# param_2 = obj.retrieve(start,end,granularity)
Explore
是的，在处理大量数据时，遍历哈希表的所有键值对确实可能导致性能问题，因为这种操作的时间复杂度是O(n)，其中n是哈希表中的元素数量。这在大数据场景下会变得低效。为了优化检索过程，可以考虑使用平衡二叉搜索树（例如红黑树）或时间轴映射的数据结构（如TreeMap在Java中）来存储日志。这些数据结构支持按时间顺序存储和检索日志，且可以在O(log n)的时间复杂度内完成插入和查找操作。特别是，可以利用这些数据结构的范围查询功能，直接找到在特定时间范围内的所有日志，无需遍历整个数据结构。