首页 > 代码库 > [Leetcode][JAVA] Max Points on a Line
[Leetcode][JAVA] 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将斜率与点个数对应起来。
需要注意的一点是特殊斜率，比如两点重复，两点横坐标相同。所以用String表示斜率比较好
获取斜率函数：
1 public String getSlope(Point p1, Point p2) 2 { 3 if(p1.x==p2.x && p1.y==p2.y) 4 return "any"; 5 else if(p1.x==p2.x) 6 return "inf"; 7 else if(p1.y==p2.y) 8 return "0"; 9 else10 {11 double temp = p2.y-p1.y;12 temp = temp/(p2.x-p1.x);13 return temp+"";14 }15 }
（由于double类型的0可能会表示成"-0.0"所以需要把纵坐标为0的情况单独列出）
每次获得两点斜率，有三种情况：1: 两点重复，增加overlap值，一重循环找出临时最多点个数tempmax后加上。2：新有效斜率： 直接放入HashMap中并把其对应点个数值置为2，以及刷新最多点个数tempmax. 3:已有斜率：更新对应斜率的点个数值（+1）， 刷新tempmax.
tempmax基础点个数为1，一重循环结束后加上重复点个数overlap，与总max值比较。
以下为代码：
1 public int maxPoints(Point[] points) { 2 if(points.length==0) 3 return 0; 4 if(points.length==1) 5 return 1; 6 if(points.length==2) 7 return 2; 8 9 int max = 2;10 for(int i=0;i<points.length;i++)11 {12 HashMap<String, Integer> hs = new HashMap<String, Integer>();13 int overlap = 0;14 int tempmax = 1;15 for(int j=i+1;j<points.length;j++)16 {17 String slp = getSlope(points[i],points[j]);18 if(slp.equals("any"))19 overlap++;20 else if(!hs.containsKey(slp))21 {22 hs.put(slp, 2);23 tempmax = Math.max(tempmax,2);24 }25 else26 {27 int number = hs.get(slp) + 1;28 hs.put(slp, number);29 tempmax = Math.max(tempmax, number);30 }31 }32 max = Math.max(max, tempmax+overlap);33 }34 return max;35 }
吐槽：double保存斜率其实不准确，最准确还是应该使用商和余数一对数字保存。
[Leetcode][JAVA] Max Points on a Line
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。