首页 > 代码库 > Leetcode:Max Points on a Line

Leetcode:Max Points on a Line

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

解题想法:

其实判断一个直线上最好的方法是判断斜率。如果在同一直线上,那么直线上一点与其他点的斜率相同。刚开始的时候利用hashmap记录下了所有相同斜率的点。但是有一点需要注意的是,有时只是平行直线,他们斜率相同,但是不在同一直线上。所以判断的准则有以下2个关键点:

1、具有相同的斜率。

2、都通过某一固定点。

还有1点容易忽略的是,可能在输入的points中存在的重复点。所以在编程过程中要特别注意。

其实从第一点开始遍历,计算第一个点与其他点的斜率,把与第一个点相同点个数记录,并计算其他点与第一个结点的斜率,统计每个斜率相同的个数。这样找出斜率相同点最大个数,并把相同结点数加上,就是与第一个结点在同一直线上的最大节点数。这样遍历下来就可以得到与每个结点在同一直线上最大节点数,这样可以记录下最大的节点数。

还有就是所有节点都为同一节点的时候,输出为n.

以下为解题代码:


public class Solution {
    public int maxPoints(Point[] points) {
        int length = points.length;
         //int max = 0;
         //double maxSlope = 0.0;
         int maxSize = 0;
         if(length<=2)
         {
             return length;
         }
         for(int i=0;i<length;i++)
         {
             HashMap<Double,Integer> map = new HashMap<Double,Integer>();
             int sameI = 0;
             int MaxI = 0;
             for(int j=i+1;j<length;j++)
             {
                 double x1 = (double)points[i].x;
                 double x2 = (double)points[j].x;
                 double y1 = (double)points[i].y;
                 double y2 = (double)points[j].y;
                 if(x1 != x2)
                 {
                     double slope = (y1 - y2)/(x1 - x2);
                     if(slope == -0.0)
                         slope = 0.0;
                     if(map.containsKey(slope))
                     {
                         int count = map.get(slope) + 1;
                         map.put(slope, count);
                     }
                     else
                     {
                         map.put(slope, 1);
                     }
                    
                 }
                 else if(y1 == y2)
                 {
                     sameI ++;
                 }
                 else
                 {
                     double key = Double.MAX_VALUE;
                     if(map.containsKey(key))
                     {
                         int count = map.get(key) + 1;
                         map.put(key, count);
                     }
                     else
                     {
                         map.put(key, 1);
                     }
                 }
             }
             if(map.size() == 0)
             {
                 MaxI = sameI + 1 ;
             }
             else
             {
                 int maxCount = 0;
                 Set<Double> set = map.keySet();
                 Iterator<Double> iter = set.iterator();
                 while(iter.hasNext())
                 {
                     double key = iter.next();
                     if(map.get(key)>maxCount)
                     {
                         maxCount = map.get(key);
                     }
                 }
                 MaxI = maxCount + sameI + 1;
             }
             if(MaxI > maxSize)
             {
                 maxSize = MaxI;
             }
         }

                 
         return maxSize;
    }
}

class Point {
   
    int x;
    int y;
    public Point()
    {
        x = 0;
        y = 0;
    }
    public Point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}