447 号问题 用python解决时 遇到超时问题

来源:4-6 灵活选择键值 Number of Boomerangs

qq_书山压力大EE_0

2018-12-01

class Solution:
    def  dis(self, a, b):
        return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])
    
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        
        res = 0
        
        for i in range(len(points)):
            maprecord = dict()
            
            for j in range(len(points)):
                if j != i:
                    va = self.dis(points[i], points[j]
                    if va not in maprecord:
                        maprecord[va]=0
                    maprecord[va] = maprecord[va] + 1
            for key in maprecord.keys():
                res += maprecord[key]*(maprecord[key]-1)
        return res
                
    
  
        

leetcode会报超时,是什么原因?
另外 python3中dict是以哈希表为底层构造的吧?, 我记得它是没有顺序性的

求老师解惑

写回答

1回答

liuyubobobo

2018-12-01

我测试了一下 你的这个代码是WA,不是TLE


是的。python3 dictionary 底层是哈希表。


不过由于Python3是解释型语言,非编译型语言,所以本身执行效率就比C++,Java要低。使用Python实现,除了注意算法的选择,对于同样的逻辑如何去写,对效率影响巨大。同样的算法,用Python如果实现的不够“好”,导致TLE很正常。前几天我刚在某OJ上用python,列表中添加元素,使用lst +=[e]的形式就超时,使用lst.append(e)的形式就ok:)


加油!:)

0
1
qq_书山压力大EE_0
非常感谢!
2018-12-01
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程