Idea: Brute force. For each point i, construct lines with all the other points. The other points may be at the same place, or vertical (slope=+Infinite) or horizontal (slope=+0). Since the lines are constructed from point i, once the slope of line (i->j) is the same as a line constructed before, j is on a line constructed before. When calculating the slope, take care 0.0!=-0.0==0.0/-1 in Java.
Time: O(n^2) Space:O(n)
Code:
public class Solution {
public int maxPoints(Point[] points) {
if(points.length==0)
{
return 0;
}
HashMap<Double,Integer> counter=new HashMap<Double,Integer>();
int result=1;
for(int i=0;i<points.length;i++)
{
counter.clear();
counter.put((double)Integer.MAX_VALUE,1);
int dup=0;
for(int j=i+1;j<points.length;j++)
{
if(points[i].x==points[j].x&&points[i].y==points[j].y)
{
dup+=1;
continue;
}
double slope=(points[i].x==points[j].x)?Integer.MAX_VALUE:0.0+(0.0+points[i].y-points[j].y)/(0.0+points[i].x-points[j].x);
if(counter.containsKey(slope))
{
counter.put(slope,counter.get(slope)+1);
}
else
{
counter.put(slope,2);
}
}
for(int number:counter.values())
{
result=Math.max(result,number+dup);
}
}
return result;
}
}
No comments:
Post a Comment