已知intervals是含有n项[start,end]的数对组,例如
代码块一是自己写的,代码块二是标准答案
代码块一
class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
n=len(intervals)
indexlist=[]
for i in range(n):
indexlist.append(intervals[i][0])
list1=sorted(indexlist)
ans=[]
for i in range(n):
x=bisect.bisect_left(list1,intervals[i][1])
if intervals[i][1]>list1[-1]:
x=-1
else:
x=indexlist.index(list1[x])
ans.append(x)
return ans
代码块二
class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
for i, interval in enumerate(intervals):
interval.append(i)
intervals.sort()
n = len(intervals)
ans = [-1] * n
for _, end, id in intervals:
i = bisect_left(intervals, [end])
if i < n:
ans[id] = intervals[i][2]
return ans
感觉自己的代码复杂度和代码块二时间复杂度都是nlogn,但是运行时间差二十倍
都是sorted,一个for循环和二分法,算下来应该是nlogn才对
希望能知道我的代码块一的时间复杂度和代码块二有没有差距
你的代码1和代码2,不是循环次数的问题,是操作的对象根本就不一样啊
代码1是新建个list,放入数据,排序
代码2是把数据放入形参里面,然后对形参进行排序
两个代码创建list和add数据的方式也不一样,这都会造成花费时间不同
此外,同样一段代码,你反复运行10次,可能10次花费时间都不同
因为电脑不是单片机,不会把所有资源都给你的代码用,它是多任务多用户的
你的花费时间多于10秒的话,时间相对会比较准确,如果是多少毫秒,基本没有参考价值