友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
149. 直线上最多的点数
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例 1：
输入：points = [[1,1],[2,2],[3,3]] 输出：3
示例 2：
输入：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)\]
这样就避免计算除法。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-07 21:55:30
*/
public int maxPoints(int[][] points) {
int length = points.length;
int result = 1;
for (int i = 0; i < length; i++) {
int[] a = points[i];
for (int j = i + 1; j < length; j++) {
int[] b = points[j];
int cnt = 2;
for (int k = j + 1; k < length; k++) {
int[] c = points[k];
int m1 = (b[0] - c[0]) * (a[1] - b[1]);
int m2 = (a[0] - b[0]) * (b[1] - c[1]);
if (m1 == m2) {
cnt++;
}
}
result = Math.max(result, cnt);
}
}
return result;
}