Solution:
How can we know that two points are on the same straight line?---> slope!!!
public class Solution {
public int maxPoints(Point[] points) {
// map: slope->count
HashMap map = new HashMap();
int max = 0;
// use equation y = k*x + b
for(int i = 0; i < points.length; i++){
// vertical to x-axis
int infinite_k = 0;
int itself = 0;
for(int j = 0; j < points.length; j++){
int x = points[j].x - points[i].x;
int y = points[j].y - points[i].y;
// itself
if(x == 0 && y == 0){
itself++;
}
else if(x == 0){
infinite_k++;
}
else{
// count the number of points that have same slope(k)
float k = (float)y / x;
if(map.containsKey(k)){
map.put(k, map.get(k)+1);
}
else{
map.put(k, 1);
}
}
}
int tmpMax = 0;
for(int tmp : map.values()){
tmpMax = Math.max(tmpMax, tmp);
}
// plus the number of duplicates for itself
max = Math.max(max, tmpMax + itself);
max = Math.max(max, infinite_k + itself);
map.clear();
}
return max;
}
}

No comments:
Post a Comment