cdsn_Python 2022-09-14 09:19 采纳率: 68.8%
浏览 27

关于算法时间复杂度的问题

问题遇到的现象和发生背景

已知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条回答

      报告相同问题?

      相关推荐 更多相似问题

      问题事件

      • 创建了问题 9月14日

      悬赏问题

      • ¥20 类似羊了个羊修改三个不同图片才能消除
      • ¥15 环绕字符串的子字符串个数(实在做不出来,只能做到普通字符串)
      • ¥20 B站评论区 点击这个蓝字就打开一张图片 是怎么做的
      • ¥15 数组并求平均数及各值与平均数之差
      • ¥15 Qt5.9.9+Vs2017遇到字符集问题
      • ¥25 win11无法启用windows功能
      • ¥15 spm-cat进行VBM分析出错
      • ¥50 c++dll中,在函数中创建线程,在函数执行完之后,线程也被销毁了,有什么办法可以让线程持续运行?
      • ¥15 微信小程序真机测试报错空白
      • ¥15 急需帮助!!!非常需要帮助