Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
public class Solution { public int maxPoints(Point[] points) { if(points==null || points.length==0) { return 0; } if(allSamePoints(points)) return points.length; int max = 0; for(int i=0;i<points.length-1;i++) { for(int j=i+1;j<points.length;j++) { if(points[j].y==points[i].y && points[j].x==points[i].x) continue; int cur = 2; for(int k=0;k<points.length;k++) { if(k!=i && k!=j && (points[k].y-points[i].y)*(points[j].x-points[i].x) ==(points[j].y-points[i].y)*(points[k].x-points[i].x)) cur++; } max = Math.max(max,cur); } } return max; } private boolean allSamePoints(Point[] points) { for(int i=1;i<points.length;i++) { if(points[0].y!=points[i].y || points[0].x!=points[i].x) return false; } return true; } }
import java.util.*; public class Solution { public int maxPoints(Point[] points) { if(points==null || points.length==0) { return 0; } HashMap<Double, Integer> map=new HashMap<Double, Integer>();; int max=1; for(int i = 0 ; i < points.length ; i++ ){ map.clear(); map.put((double)Integer.MIN_VALUE, 1); int dup = 0; for(int j = i+1;j<points.length ; j++ ){ if(points[j].x==points[i].x&&points[j].y==points[i].y){ dup++; continue; } double key = points[j].x - points[i].x == 0 ? Integer.MIN_VALUE: 0+(double)(points[j].y-points[i].y)/(double)(points[j].x-points[i].x); if(map.containsKey(key)){ map.put(key,map.get(key) +1); } else{ map.put(key,2); } } for (int temp: map.values()){ // duplicate may exist if (temp+dup>max){ max=temp+dup; } } } return max; } }