首页 > 代码库 > Problem Max Points On a Line
Problem Max Points On a Line
Problem Description:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution:
1 public int maxPoints(Point[] points) { 2 if (points.length <= 1) { 3 return points.length; 4 } 5 Map<Double, Integer> map = new HashMap<Double, Integer>(); 6 int maxPoints = 0; 7 for (int i = 0; i < points.length; i++) { 8 map.clear(); 9 int samePointCount = 1;10 int max = 0;11 for (int j = i+1; j < points.length; j++) {12 if (points[i].x == points[j].x &&13 points[i].y == points[j].y) {14 samePointCount++;15 } else {16 double slope = Double.MAX_VALUE;17 if (points[i].y == points[j].y) {18 slope = 0;19 }20 else if (points[i].x != points[j].x) 21 slope = (points[i].y - points[j].y) / (double) (points[i].x - points[j].x);22 if (! map.containsKey(slope)) {23 map.put(slope, 1);24 } else {25 map.put(slope, map.get(slope)+1);26 }27 28 if (map.get(slope) > max) {29 max = map.get(slope);30 }31 32 }33 }34 if (max + samePointCount > maxPoints) {35 maxPoints = max + samePointCount ;36 }37 }38 return maxPoints;39 40 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。