LeetCode「判断是否为直线」算法如何优化运行时与内存性能?
「判断是否为直线」题目的性能优化思路
现有代码排名靠后的核心原因
- 引入重量级第三方依赖:代码在函数内部导入
numpy的操作本身会带来极高的导入开销,不仅拖慢运行时速度,也会拉高内存占用——为了实现一个简单的去重功能引入整个数值计算库,属于严重的性能浪费。 - 存在不必要的IO操作:代码分支判断中的
print(slope)会触发标准输出写入,这类IO操作的耗时远高于纯算术运算,是拉低Runtime排名的核心原因之一。 - 冗余的内存与计算开销:需要把所有相邻点计算出的斜率存入列表,既会占用额外的列表内存,浮点除法的运算效率也远低于整数运算,还可能因为浮点精度问题出现判断误差。
- 原逻辑存在边界漏洞:遇到x坐标差为0的垂直直线场景,直接把x值存入斜率列表,碰到多段垂直但x坐标不统一的折线时,会出现逻辑误判。
高效解题的核心逻辑
核心思路是用向量叉积替代斜率计算,全程规避除法、浮点运算与额外存储:
三个点共线的充要条件是,以第一个点为公共起点,连接第二个点的向量、连接当前待判断点的向量,二者的叉积为0。对应的判断公式为:(x1 - x0) * (yi - y0) == (xi - x0) * (y1 - y0)
这种思路的优势非常明显:
- 全程仅使用整数运算,没有除法、没有浮点精度问题,计算速度远快于传统的斜率计算逻辑
- 不需要申请额外列表存储所有斜率,遍历过程中一旦发现叉积不为0,直接返回结果,无需走完所有坐标点
- 天然兼容垂直直线、水平直线的特殊场景,不需要单独做除零判断
- 完全不需要第三方库支撑,纯原生Python即可实现
优化后的参考代码
def checkStraightLine(self, coordinates): # 取前两个点作为共线判断的基准 (x0, y0), (x1, y1) = coordinates[0], coordinates[1] # 遍历剩余点做叉积判断 for x, y in coordinates[2:]: if (x1 - x0) * (y - y0) != (x - x0) * (y1 - y0): return False return True
该实现没有冗余操作,运行时和内存占用通常可以超过90%以上的同题目提交。
内容的提问来源于stack exchange,提问作者Avia Y
相关产品推荐
相关产品推荐

