首页 > 代码库 > LeetCode: Max Points on a Line 解题报告
LeetCode: Max Points on a Line 解题报告
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.
SOLUTION 1:
全部的点扫一次，然后计算每一个点与其它点之间的斜率。
创建一个MAP, KEY-VALUE是 斜率：线上的点的数目。
另外，注意重合的点，每次都要累加到每一条线上。
注意：
1. k = 0 + (double)(points[i].y - points[j].y)/(double)(points[i].x - points[j].x);
使用这个公式来计算的原因是 (double)(points[i].y - points[j].y)/(double)(points[i].x - points[j].x) 有可能计算出0和-0
0+(-0)后，就会都变成0.
2. 用Dup来计算重合的点。
3. 如果某点开始所有的点都在一起，则至少Max = Math.max(max, duplicate)。
4. 注意每次换一个点计算时，map要重建。因为即使K相同，只代表线是平等，不代表会是同一条线。
1 public class Solution { 2 public int maxPoints(Point[] points) { 3 int max = 0; 4 5 if (points == null) { 6 return 0; 7 } 8 9 int len = points.length;10 11 for (int i = 0; i < len; i++) {12 // Create a map to recode all the numbers of elements of every K.13 HashMap<Double, Integer> map = new HashMap<Double, Integer>();14 15 // ItSelf.16 int dup = 0;17 18 for (int j = i; j < len; j++) {19 // the same point.20 if (points[i].x == points[j].x && points[i].y == points[j].y) {21 dup++;22 continue;23 }24 25 double k = Double.MAX_VALUE;26 if (points[i].x != points[j].x) {27 k = 0 + (double)(points[i].y - points[j].y)/(double)(points[i].x - points[j].x);28 }29 30 if (map.containsKey(k)) {31 map.put(k, map.get(k) + 1);32 } else {33 map.put(k, 1);34 }35 }36 37 max = Math.max(max, dup);38 for (int n: map.values()) {39 max = Math.max(max, n + dup);40 }41 }42 43 return max;44 }45 }
主页君的GitHub:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/hash/MaxPoints.java
参考答案：
http://www.ninechapter.com/solutions/max-points-on-a-line/
LeetCode: Max Points on a Line 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。