Commit2fada19

applewjg

committed

Max Points on a line

Change-Id: I46f37795eec9462c942f4b5e87c74b800b6ce195

1 parenta224661 commit2fada19Copy full SHA for 2fada19

File tree

+46

-0

lines changed

+46

-0

lines changed

Lines changed: 46 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,46 @@`
	`1`	`+/*`
	`2`	`+ Author: Andy, nkuwjg@gmail.com`
	`3`	`+ Date: Dec 03, 2014`
	`4`	`+ Problem: Max Points On a Line`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Notes:`
	`7`	`+ Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.`
	`8`	`+ Solution: 1. hashmap. Time: O(n^2), Space: O(n);`
	`9`	`+*/`
	`10`	`+`
	`11`	`+/**`
	`12`	`+ * Definition for a point.`
	`13`	`+ * class Point {`
	`14`	`+ * int x;`
	`15`	`+ * int y;`
	`16`	`+ * Point() { x = 0; y = 0; }`
	`17`	`+ * Point(int a, int b) { x = a; y = b; }`
	`18`	`+ * }`
	`19`	`+ */`
	`20`	`+publicclassSolution {`
	`21`	`+publicintmaxPoints(Point[]points) {`
	`22`	`+intres =0;`
	`23`	`+intN =points.length;`
	`24`	`+for (inti =0;i <N; ++i) {`
	`25`	`+HashMap<Double,Integer>m =newHashMap<Double,Integer>();`
	`26`	`+intss =1,sp =0;`
	`27`	`+for (intj =i +1;j <N; ++j) {`
	`28`	`+doubleslope =Double.MIN_VALUE;`
	`29`	`+if (points[i].x !=points[j].x) {`
	`30`	`+slope = (double)(points[i].y -points[j].y) / (points[i].x -points[j].x);`
	`31`	`+if (slope == -0.0)slope =0.0;`
	`32`	`+ }elseif (points[i].y ==points[j].y) {`
	`33`	`+sp +=1;continue;`
	`34`	`+ }`
	`35`	`+inttmp =2;`
	`36`	`+if (m.containsKey(slope)) {`
	`37`	`+tmp =m.get(slope) +1;`
	`38`	`+ }`
	`39`	`+m.put(slope,tmp);`
	`40`	`+ss =Math.max(ss,tmp);`
	`41`	`+ }`
	`42`	`+res =Math.max(res,ss +sp);`
	`43`	`+ }`
	`44`	`+returnres;`
	`45`	`+ }`
	`46`	`+}`

Comments

(0)