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回答
-
我测试了一下 你的这个代码是WA,不是TLE
是的。python3 dictionary 底层是哈希表。
不过由于Python3是解释型语言,非编译型语言,所以本身执行效率就比C++,Java要低。使用Python实现,除了注意算法的选择,对于同样的逻辑如何去写,对效率影响巨大。同样的算法,用Python如果实现的不够“好”,导致TLE很正常。前几天我刚在某OJ上用python,列表中添加元素,使用lst +=[e]的形式就超时,使用lst.append(e)的形式就ok:)
加油!:)
012018-12-01
相似问题
447超时问题
回答 1