难度: Hard
Submission
运行时间: 232 ms
内存: 18.9 MB
class AutocompleteSystem:
def refresh(self):
self.sentences = [item[1] for item in self.sorted_lists]
self.idx = 0
self.inp = ""
def insert(self, time, sentence):
for i in range(len(self.sorted_lists)):
if (self.sorted_lists[i][0] < time) or \
(self.sorted_lists[i][0] == time and self.sorted_lists[i][1] >= sentence):
self.sorted_lists.insert(i, (time, sentence))
return
self.sorted_lists.append((time, sentence))
def pop(self, sentence):
for i in range(len(self.sorted_lists)):
if self.sorted_lists[i][1] == sentence:
time = self.sorted_lists[i][0]
del self.sorted_lists[i]
return time
return 0
def __init__(self, sentences: List[str], times: List[int]):
self.sorted_lists = sorted(zip(times, sentences), key=lambda x: (-x[0], x[1]))
self.refresh()
def input(self, c: str) -> List[str]:
if c == "#":
time = self.pop(self.inp)
self.insert(time+1, self.inp)
self.refresh()
'''for _, s in self.sorted_lists:
print(s)
print()'''
return []
self.inp += c
new_sentences = []
for s in self.sentences:
if len(s) > self.idx and s[self.idx] == c:
new_sentences.append(s)
self.sentences = new_sentences
self.idx += 1
return new_sentences[:3]
# Your AutocompleteSystem object will be instantiated and called as such:
# obj = AutocompleteSystem(sentences, times)
# param_1 = obj.input(c)
Explain
这个题解使用了一个排序列表来维护输入的句子和它们的频率。每次输入字符时，它都会筛选出以该字符开头的所有句子，并返回最频繁的前三个。当输入'#'时，它会增加当前输入句子的频率，并重新排序列表。
时间复杂度: O(n)
空间复杂度: O(n)
class AutocompleteSystem:
def refresh(self):
self.sentences = [item[1] for item in self.sorted_lists] # 刷新缓存的句子列表
self.idx = 0 # 重置当前输入字符的索引
self.inp = "" # 清空当前输入
def insert(self, time, sentence):
for i in range(len(self.sorted_lists)):
if (self.sorted_lists[i][0] < time) or \ # 插入新句子并保持列表按频率和字典序排序
(self.sorted_lists[i][0] == time and self.sorted_lists[i][1] >= sentence):
self.sorted_lists.insert(i, (time, sentence))
return
self.sorted_lists.append((time, sentence))
def pop(self, sentence):
for i in range(len(self.sorted_lists)): # 查找并删除指定句子，返回其频率
if self.sorted_lists[i][1] == sentence:
time = self.sorted_lists[i][0]
del self.sorted_lists[i]
return time
return 0
def __init__(self, sentences: List[str], times: List[int]):
self.sorted_lists = sorted(zip(times, sentences), key=lambda x: (-x[0], x[1])) # 初始化排序列表
self.refresh()
def input(self, c: str) -> List[str]:
if c == "#":
time = self.pop(self.inp) # 更新当前输入句子的频率
self.insert(time+1, self.inp)
self.refresh() # 重新刷新缓存的句子列表
return []
self.inp += c # 添加新字符到当前输入
new_sentences = []
for s in self.sentences: # 筛选出以当前输入开头的句子
if len(s) > self.idx and s[self.idx] == c:
new_sentences.append(s)
self.sentences = new_sentences
self.idx += 1
return new_sentences[:3] # 返回最频繁的前三个句子
# Your AutocompleteSystem object will be instantiated and called as such:
# obj = AutocompleteSystem(sentences, times)
# param_1 = obj.input(c)
Explore
按频率降序排列确保了最常用的句子能够被更快地访问和返回，这是因为用户更可能搜索高频句子。字典序升序排列则是为了在频率相同的情况下提供一致且可预测的排序顺序。这种排序方式对性能的主要影响是初始化时的排序操作需要O(n log n)的时间复杂度，但它简化了后续的检索操作，因为可以直接获取列表的前三个元素来快速返回最常见的搜索结果。
当输入字符为'#'时，意味着用户完成了一次完整的句子输入。先调用`pop`方法是为了获取并删除当前输入句子的旧频率（如果存在），这样可以确保句子列表中不会有重复项。随后调用`insert`方法增加该句子的频率（旧频率基础上加1），然后重新插入到排序列表中。这样处理可以确保句子列表始终保持正确的按频率排序，且句子频率更新是高效且准确的。
在`pop`方法中，返回0表示指定的句子在列表中不存在，即该句子之前未被输入过。返回0的特殊意义在于它可以被`insert`方法使用来作为该新句子的初始频率（0+1=1）。这样的设计保证了系统能够处理新句子的加入，且在没有先前记录的情况下也能正确地更新其频率。
在每次输入非'#'字符后，更新`self.sentences`和`self.idx`的目的是为了缩小搜索范围并正确地跟踪用户的当前输入状态。这样设计的优点是可以减少每次查询的计算量，因为只需在缩小的句子集合中进行搜索，这提高了搜索效率。缺点是，每次字符输入都需要进行数组操作（如过滤和索引更新），这可能在输入较长或句子库较大时影响性能。