1. duplicate points;
2. share lines parallel to y-axis;
3. share lines parallel to x-axis;
4. slopes.
Use a HashMap to store <slope, number of points> pair.
class Point {
int x;
int y;
Point() { x = 0; y = 0; }
Point(int a, int b) { x = a; y = b; }
}
public class MaxPointsonALine {
public int maxPoints(Point[] points) {
if (points == null || points.length == 0)
return 0;
HashMap hm = new HashMap();
int max = 1;
for (int i = 0; i < points.length; i++)
{
//Reinitialize the map since the shared points of each point are different
hm.clear();
//put the point itself into the map, use Integer_MIN_VALUE as the key
hm.put((double)Integer.MIN_VALUE, 1);
//in case there are duplicates in the array
int dupli = 0;
//all the shared points prior to i has been checked in the previous loops, thus we only need to
//consider shared points after i
for (int j = i + 1; j < points.length; j++)
{
//here comes the duplicates
if (points[j].x == points[i].x && points[j].y == points[i].y)
{
dupli++;
continue;
}
double key = 0.0;
//share a line parallel to y-axis, we know the slop = infinity
if (points[j].x == points[i].x)
key = (double)Integer.MAX_VALUE;
//just the slope
// because (double)0/-1 is -0.0, so we should use 0.0+-0.0=0.0 to solve 0.0 !=-0.0
// problem
else
key = 0.0 +
(double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
if (!hm.containsKey(key))
hm.put(key, 2);
else
hm.put(key, hm.get(key) + 1);
}
//now we add duplicates to the values in the map and compare them with the max
for (int tmp : hm.values())
{
if (tmp + dupli > max)
max = tmp + dupli;
}
}
return max;
}
}
No comments:
Post a Comment