Max Points on a Line
Source
Given n points on a 2D plane, find the maximum number of points that lie
on the same straight line.
Example
Given 4 points: (1,2), (3,6), (0,0), (1,3).
The maximum number is 3.
Java
public class Solution {
public int maxPoints(Point[] points) {
int globalMax = 0;
if (points == null || points.length==0) {
return 0;
}
int len = points.length;
for (int i = 0; i < len; i++) {
HashMap<Double, Integer> map = new HashMap<Double, Integer>();
int dup = 0;
int vertical=0;
int localMax=0;
for (int j = i+1; j < len; j++) {
if (points[i].x == points[j].x) {
if(points[i].y == points[j].y){
dup++;
}
else{
vertical++;
}
continue;
}
double k = 0+(double)(points[i].y - points[j].y)/(double)(points[i].x - points[j].x);
if (map.containsKey(k)) {
map.put(k, map.get(k) + 1);
} else {
map.put(k, 1);
}
localMax = Math.max(localMax, map.get(k));
}
localMax = Math.max(localMax, vertical)+dup+1;
globalMax = Math.max(globalMax,localMax);
}
return globalMax;
}
}