Max Points on a Line, Leetcode 解题笔记

Given n points on a 2D plane,
find the maximum number of points that lie on the same straight line.



remember that a line can be represented by y=kx+d, if p1 and p2 are in same line, then y1=x1k+d,
y2=kx2+d, so y2-y1=kx2-kx1, so k=(y2-y1)/(x2-x1), then we can apply this formular to check
if two points are in same line, however how to handle the duplicate points problem?
So instead to calculate the line with maximum points , we should calculate
longest line(maximum ponts) through same point

 * 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) {
	        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++){
	            // shared point changed, map should be cleared and server the new point
	            // maybe all points contained in the list are same points,and same points' k is 
	            // represented by Integer.MIN_VALUE
	            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){
	               // look 0.0+(double)(points[j].y-points[i].y)/(double)(points[j].x-points[i].x)
	               // because (double)0/-1 is -0.0, so we should use 0.0+-0.0=0.0 to solve 0.0 !=-0.0
	               // problem
	               // if the line through two points are parallel to y coordinator, then K(slop) is 
	               // Integer.MAX_VALUE
	               double key=points[j].x-points[i].x==0?Integer.MAX_VALUE:0.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);
	                  map.put(key, 2);
	          for (int temp: map.values()){
	              // duplicate may exist
	              if (temp+dup>max){
	        return max;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s