Skip to content

0149-max-points-on-a-line.adoc

Latest commit

 

History

History
79 lines (57 loc) · 1.76 KB

0149-max-points-on-a-line.adoc

File metadata and controls

79 lines (57 loc) · 1.76 KB
Raw

149. 直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

{image_attr} 
输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

{image_attr} 
输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

提示：

  • 1 <= points.length <= 300

  • points[i].length == 2

  • -104 <= xi, yi <= 104

  • points 中的所有点 互不相同

思路分析

先确定两个点，然后再选一个点，计算三个点的斜率来查看是否在同一条直线。

\$(y_1 - y_2) / (x_1 - x_2) = (y_2 - y_3)/(x_2 - x_3)\$

等价于

\$(x_2 - x_3)* (y_1 - y_2) = (x_1 - x_2) * (y_2 - y_3)\$

这样就避免计算除法。

一刷
link:{sourcedir}/_0149_MaxPointsOnALine.java[role=include]
二刷
link:{sourcedir}/_0149_MaxPointsOnALine_2.java[role=include]