Solution 1: Method is brute force, but use 2 layer of Hash table to store the slop (dy/dx) and deal with the corn case.
public class Solution {
public int maxPoints(Point[] points) {
int n=points.length;
Map<Integer,Map<Integer,Integer>> map=new HashMap<>();
int res=0;
for (int i=0; i<n; i++) {
map.clear();
int overlap=0, max=0;
for (int j=i+1; j<n; j++) {
int x=points[j].x-points[i].x;
int y=points[j].y-points[i].y;
if (x==0) {
if (y==0) {
overlap++;
continue;
}
else y=1;
}
else if (y==0) x=1;
else {
int gcd=calGcd(x,y);
x=x/gcd;
y=y/gcd;
}
int count=1;
if (!map.containsKey(x)) {
Map<Integer,Integer> one=new HashMap<>();
one.put(y,1);
map.put(x,one);
}
else if (!map.get(x).containsKey(y)) {
map.get(x).put(y,1);
}
else {
count=map.get(x).get(y);
map.get(x).put(y,++count);
}
max=Math.max(max,count);
}
res=Math.max(res,max+overlap+1);
}
return res;
}
private int calGcd(int x, int y) {
while (y!=0) {
int temp=y;
y=x%y;
x=temp;
}
return x;
}
}
没有评论:
发表评论