V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
getlost
V2EX  ›  LeetCode

同样的思路,计算时间确实别人的百倍

  •  
  •   getlost · 2019-03-10 21:33:49 +08:00 · 15026 次点击
    这是一个创建于 1844 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最近在在刷 LeetCode,已经刷到 15 题了,但是在 15 题这卡住了,特来请教。以下是我的代码

    class Solution:
        def threeSum(self, nums):
            negative = []
            negative_again = []
            positive = []
            positive_again = []
            zero = []
            answer = []
            m, n = 0, 0
    
            for value in nums:
                if value < 0:
                    if -value not in negative:
                        negative.insert(0, -value)
                    elif -value not in negative_again:
                        negative_again.append(-value)
                elif value > 0:
                    if value not in positive:
                        positive.append(value)
                    elif value not in positive_again:
                        positive_again.append(value)
                else:
                    zero.append(value)
            positive.sort()
            negative.sort()
    
            if len(zero) > 2:
                answer.append([0, 0, 0])
    
            if len(positive) == 0 or len(negative) ==0:
                return answer
    
            for i in negative:  # [i, 0, -i] # 第一个 for
                n = 1 + n
                if i > positive[-1]:
                    break
    
                for j in negative[n:]:  # [i, j, -i-j]
                    ij = i + j
                    #print(i, i, ij)
                    if ij > positive[-1]:
                        break
    
                    if ij in positive:
                        pre_answer = [-j, -i, ij]
                        answer.append(pre_answer)
            
            for i in positive: # 第二个 for
                m = m + 1
                if i > negative[-1]:
                    break
                for j in positive[m:]:
                    ij = i + j
                    if ij > negative[-1]:
                        break
    
                    if ij in negative:
                        pre_answer = [i, j, -ij]
                        answer.append(pre_answer)
                        
            if len(zero) > 0:   
                for i in positive:
                    if i in negative:
                        answer.append([-i, 0, i])
            
            for i in negative_again:
                if (i + i) in positive:
                    pre_answer = [-i, -i, i+i]
                    answer.append(pre_answer)
    
            for i in positive_again:
                if (i + i) in negative:
                    pre_answer = [ -i-i, i, i]
                    answer.append(pre_answer)
                                                        
            return answer
    

    这里是第一名的代码(我借鉴他的思路写的,但是速度差了 100 倍)

    
    
    class Solution:
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            out = []
            zero = 0
            positive, negative = {}, {}
            p_max = 0
            n_min = 0
            import itertools
            if not nums:
                return out
    
            for i in nums:
                if i > 0:
                    positive[i] = positive.get(i, 0) + 1
                    if i > p_max:
                        p_max = i
                elif i < 0:
                    negative[i] = negative.get(i, 0) + 1
                    if i < n_min:
                        n_min = i
                else:
                    zero += 1
            if len(positive) == 0 or len(negative) == 0:
                if zero > 2:
                    out.append([0, 0, 0])
                return out
    
            p = sorted(positive.keys())
            for i in range(len(p)):  # 第一个 for
                if p[i] > -n_min:
                    break
                for j in range(i+1, len(p)):
                    s = p[i]+p[j]
                    if s > -n_min:
                        break
                    if -s in negative:
                        out.append([p[i], p[j], -s])
    
                if positive[p[i]] >= 2:
                    if -(p[i]*2) in negative:
                        out.append([p[i], p[i], -(p[i]*2)])
    
            n = sorted([-k for k in negative])
            for i in range(len(n)): # 第二个 for
                if n[i] > p_max:
                    break
                for j in range(i + 1, len(n)):
                    s = n[i] + n[j]
                    if s > p_max:
                        break
                    if s in positive:
                        out.append([-n[i], -n[j], s])
    
                if negative[-n[i]] >= 2:
                    if (n[i]*2) in positive:
                        out.append([-n[i], -n[i], (n[i]*2)])
    
    
            if zero > 0:
                for i in positive:
                    if -i in negative:
                        out.append([i,0,-i])
            if zero > 2:
                out.append([0, 0, 0])
    
            return out
    
    
    

    我导入了 timeit,计算了一下时间,差别在 for 循环的块里(就是我注释的两个 for 循环),排查了两晚上,也没找到答案。

    10 条回复    2019-03-12 07:20:34 +08:00
    getlost
        1
    getlost  
    OP
       2019-03-10 21:36:01 +08:00
    wallriding
        2
    wallriding  
       2019-03-10 21:43:24 +08:00
    这题需要写这么长吗?
    getlost
        3
    getlost  
    OP
       2019-03-10 22:04:39 +08:00
    @wallriding 刚开始练习,还需要努力学习
    wallriding
        4
    wallriding  
       2019-03-10 22:18:06 +08:00
    @getlost 你直接看 discussion 里最高票帖子呀
    getlost
        5
    getlost  
    OP
       2019-03-10 22:24:37 +08:00
    @wallriding 第二段代码是耗时最短的解法,我参考他的解法来做了一次,但是存在疑问,因为用了同样的逻辑,耗时却差了 100 倍,我很疑惑,不知道哪里理解错了。
    Gakho
        6
    Gakho  
       2019-03-11 10:31:10 +08:00
    试过 copy 第一名的解法直接提交,时间也会出现差了一半以上,说实话对于这个时间我大多数抱着看看就好的心态
    getlost
        7
    getlost  
    OP
       2019-03-11 12:40:37 +08:00
    @Gakho 我本地试的,同样的参数,他的就是比我快 100 倍,为啥还不知道
    hanbaobao2005
        8
    hanbaobao2005  
       2019-03-11 17:37:17 +08:00
    insert 的效率很差,不建议使用
    getlost
        9
    getlost  
    OP
       2019-03-11 20:23:02 +08:00
    @hanbaobao2005 学习了,之前没了解过。我导入 timeit 模块,发现我的两个 for 循环占用的时间占总时间的 99%,不太明白为什么?
    hanbaobao2005
        10
    hanbaobao2005  
       2019-03-12 07:20:34 +08:00
    @getlost 替换 insert 试过了么?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5144 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 473ms · UTC 09:42 · PVG 17:42 · LAX 02:42 · JFK 05:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.