首页 > 代码库 > [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.
https://oj.leetcode.com/problems/max-points-on-a-line/
思路：以每一个点位轴点，计算其他点的斜率，如果斜率相同则共线，用hashmap记录共线点数，不断更新最大值。
注意：有重复点需要处理，尤其是所有点都是重复点的情况需要特殊处理。
import java.util.HashMap;import java.util.Map;/** * http://blog.csdn.net/xhu_eternalcc/article/details/24556553 * http://www.cnblogs.com/TenosDoIt/p/3444086.html * @author jd * */public class Solution { public int maxPoints(Point[] points) { if (points == null) return 0; int n = points.length; if (n <= 2) return n; Map<Double, Integer> map = new HashMap<Double, Integer>(); int maxN = 0; for (int i = 0; i < points.length; i++) { map.clear(); Point cur = points[i]; int duplicates = 1; boolean notAllDup = false; for (int j = 0; j < points.length; j++) { if (j == i) continue; if (points[i].x == points[j].x && points[i].y == points[j].y) { duplicates++; } else { notAllDup = true; Double slope = slope(cur, points[j]); if (map.get(slope) == null) { map.put(slope, 1); } else { map.put(slope, map.get(slope) + 1); } } } if (!notAllDup) { maxN = Math.max(maxN, duplicates); } for (Double key : map.keySet()) { maxN = Math.max(maxN, map.get(key) + duplicates); } } return maxN; } private double slope(Point cur, Point p) { int x1 = cur.x; int y1 = cur.y; int x2 = p.x; int y2 = p.y; if (x1 == x2 && y1 == y2) { return -Double.MAX_VALUE; } else if (x1 == x2) return Double.MAX_VALUE; else if (y1 == y2) return 0; else return 1.0 * (y2 - y1) / (x2 - x1); } public static void main(String[] args) { Point[] points = null; // 3 points = new Point[] { new Point(1, 1), new Point(2, 2), new Point(3, 3), new Point(9, 10), new Point(10, 9) }; System.out.println(new Solution().maxPoints(points)); // 5 points = new Point[] { new Point(1, 1), new Point(2, 2), new Point(3, 3), new Point(10, 10), new Point(9, 9) }; System.out.println(new Solution().maxPoints(points)); // 3 points = new Point[] { new Point(1, 1), new Point(0, 0), new Point(1, 1) }; System.out.println(new Solution().maxPoints(points)); // 3 points = new Point[] { new Point(1, 1), new Point(1, 1), new Point(1, 1) }; System.out.println(new Solution().maxPoints(points)); // 3 points = new Point[] { new Point(1, 1), new Point(1, 1), new Point(1, 0) }; System.out.println(new Solution().maxPoints(points)); // 1 points = new Point[] { new Point(1, 1) }; System.out.println(new Solution().maxPoints(points)); // 2 points = new Point[] { new Point(1, 1), new Point(1, 1) }; System.out.println(new Solution().maxPoints(points)); // 2 points = new Point[] { new Point(0, 0), new Point(1, 1), new Point(1, -1) }; System.out.println(new Solution().maxPoints(points)); }}
参考：
http://blog.csdn.net/xhu_eternalcc/article/details/24556553
http://www.cnblogs.com/TenosDoIt/p/3444086.html
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。