之前写过这个题目的排序+二分查找方案，今天收到评论指出程序中的问题。原来代码每次拿到都需要排序，排序的平均时间复杂度是O(nlogn)。优点是O(logn)的一次搜索避免了扫描所有元素。整体时间复杂度为O(nlogn)。实际上，如果扫描完所有元素，时间复杂度为o(n)。貌似使用排序+二分查找，时间复杂度更高。我重新写了一个扫描所有元素的代码，发现耗时反而会长一些。因为实际运行时间与操作顺序、数量、数据本身有关。也关系到排序算法的具体实现。如果插入操作少，查询操作多，或者虽然插入操作多，列表元素多，但是插入操作比较集中，排序是插入排序，那么每次重新排序使用的操作数可能很少（如果是普通快速排序，列表基本有序时排序效率很低，接近n^2）扫描所有元素代码importbisectclassTweetCounts:def__init__(self):self.ul={}defrecordTweet(self,tweetName:str,time:int)->无：如果tweetName不在self.ul中：self.ul[tweetName]=[]self.ul[tweetName].append(time)defgetTweetCountsPerFrequency(self,freq:str,tweetName:str,startTime:int,endTime:int)->List[int]:iffreq=='minute':f=60eliffreq=='hour':f=3600else:f=86400结果=[0]*math.ceil((endTime-startTime+1)/f)fortinself.ul[tweetName]:ifstartTime<=t<=endTime:result[(t-startTime)//f]+=1返回结果原始方法代码importbisectclassTweetCounts:def__init__(self):self.ul={}defrecordTweet(self,tweetName:str,time:int)->None:如果tweetName不在self.ul:self.ul[tweetName]=[]self.ul[tweetName].append(time)defgetTweetCountsPerFrequency(self,freq:str,tweetName:str,startTime:int,endTime:int)->List[int]:self.ul[tweetName].sort()#print(self.ul[tweetName])iffreq=='minute':f=60eliffreq=='hour':f=3600else:f=86400b=bisect.bisect(self.ul[tweetName],startTime-1)ans=[]cnt=0limit=startTime+fforninself.ul[tweetName][b:]:#print(n)ifn>endTime:ans.append(cnt)r=(endTime-limit)//fiflimit
