给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
代码
- 利用hash存储
- 求斜率
class Solution {
public int maxPoints(int[][] points) {
int n = points.length;
if (n == 0) return 0;
if (n == 1) return 1;
int res = 0;
for (int i = 0; i < n - 1; i++) {
Map<String, Integer> slope = new HashMap<>();
int repeat = 0;
int tmp_max = 0;
for (int j = i + 1; j < n; j++) {
int dy = points[i][1] - points[j][1];
int dx = points[i][0] - points[j][0];
if (dy == 0 && dx == 0) {
repeat++;
continue;
}
int g = gcd(dy, dx);
if (g != 0) {
dy /= g;
dx /= g;
}
String tmp = String.valueOf(dy) + "/" + String.valueOf(dx);
slope.put(tmp, slope.getOrDefault(tmp, 0) + 1);
tmp_max = Math.max(tmp_max, slope.get(tmp));
}
res = Math.max(res, repeat + tmp_max + 1);
}
return res;
}
private int gcd(int dy,int dx) {
if (dx = 0) return dy;
else {return gcd(dx,dy%dx)}
}
}
// 作者：powcai
// 链接：https://leetcode-cn.com/problems/max-points-on-a-line/solution/yong-xie-lu-by-powcai/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
7mm
class Solution {
public int maxPoints(int[][] points) {
if (points == null) {
return 0;
}
int len = points.length;
if (len <= 2) {
return len;
}
int max = 2;
for (int i = 0; i < len - 2; i++) {
int same = 0;
for (int j = i + 1; j < len; j++) {
int cnt = 1;
long diffx = points[i][0] - points[j][0];
long diffy = points[i][1] - points[j][1];
if (diffx == 0 && diffy == 0) {
same++;
} else {
cnt++;
for (int k = j + 1; k < len; k++) {
if (diffx * (points[i][1] - points[k][1]) == diffy * (points[i][0] - points[k][0])) {
cnt++;
}
}
}
max = Math.max(max, same + cnt);
}
if (max > len / 2) {
break;
}
}
return max;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
