Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution:
We first create a map of the points and the number of appearances. Then we traverse the array in a double loop to create all the possible lines keeping them in a HashMap, thus we have to override the equals and hashCode. We also keep the points in each Line instance.
The whole algorithm runs in $O(n^2)$.
The whole algorithm runs in $O(n^2)$.
/** * Definition for a point. * class Point { * int x; * int y; * Point() { x = 0; y = 0; } * Point(int a, int b) { x = a; y = b; } * } */ public class Solution { public int maxPoints(Point[] points) { int nPoints = 0; //Remove duplicates HashMap<Point, Integer> pointMap = new HashMap<Point, Integer>(); for(int i=0; i<points.length; i++) { if(!pointMap.containsKey(points[i])) pointMap.put(points[i],0); pointMap.put(points[i],pointMap.get(points[i])+1); } HashMap<Line, Line> lines = new HashMap<Line, Line>(); Point[] points2 = pointMap.keySet().toArray(new Point[0]); for(int i=0; i<points2.length-1; i++) { for(int j=i+1; j<points2.length; j++) { Line l = new Line(points2[i],points2[j],pointMap.get(points2[i]),pointMap.get(points2[j])); if(!lines.containsKey(l)) lines.put(l,l); else { lines.get(l).addPoint(points2[i], pointMap.get(points2[i])); lines.get(l).addPoint(points2[j], pointMap.get(points2[j])); } nPoints = lines.get(l).getNumberPoints() > nPoints ? lines.get(l).getNumberPoints() : nPoints; } } return nPoints>0 ? nPoints : points.length; } public class Line { double yo; double slope; int nPoints=0; HashSet<Point> pointsLine; public Line(Point p1, Point p2, int p1Apearances, int p2Apearances) { if(p2.x == p1.x) { slope = Double.POSITIVE_INFINITY; yo = p2.x*1.0; } else { slope = 1.0*(p1.y-p2.y)/(p1.x-p2.x); yo = p1.y-slope*p1.x; } pointsLine = new HashSet<Point>(); addPoint(p1, p1Apearances); addPoint(p2, p2Apearances); } public void addPoint(Point p1, int nAppearances) { if(!pointsLine.contains(p1)) { pointsLine.add(p1); nPoints+=nAppearances; } } public int getNumberPoints() { return nPoints; } public boolean equals(Object o) { if(!(o instanceof Line)) return false; Line otherLine = (Line) o; return otherLine.yo == yo && otherLine.slope == slope; } public int hashCode() { int hash = 3; hash = hash * 7 + Double.valueOf(yo).hashCode(); hash = hash * 7 + Double.valueOf(slope).hashCode(); return hash; } } }
No comments :
Post a Comment