rainyzz's blog

Max Points on a Line

###Max Points on a Line https://oj.leetcode.com/problems/max-points-on-a-line/

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

这个题的思路就是找数组里的两个点,用这两个点来做一条直线,然后看数组里的点都在直线上不,我用的是两点式,需要考虑两个点x或y坐标相同的特殊情况。

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
26
27
28
29
30
31
32
33
public class Solution {
public int maxPoints(Point[] points) {
int num = points.length;
int maxPoints = 0;
if(num == 1) return 1;
for(int first = 0; first < num; first++){
for(int second = 0;second < num / 2 +1; second++){
if(first == second) continue;
Point firstPoint = points[first];
Point secondPoint = points[second];
int count = 0;
if(firstPoint.x == secondPoint.x){
for(int i = 0; i < num; i++){
if(points[i].x == firstPoint.x) count++;
}
}else if(firstPoint.y == secondPoint.y){
for(int i = 0; i < num; i++){
if(points[i].y == firstPoint.y) count++;
}
}else{
for(int i = 0; i < num; i++){
if((points[i].y - secondPoint.y) * (firstPoint.x - secondPoint.x) ==
(firstPoint.y - secondPoint.y) * (points[i].x - secondPoint.x)){
count++;
}
}
}
if(count > maxPoints) maxPoints = count;
}
}
return maxPoints;
}
}