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://leetcode.com/problems/max-points-on-a-line/

 

问题分析

　　给定一个平面上若干个点来说，要计算有多少个点在一条线上，我们需要选择每个节点作为起点，看它到所有其他的点能连成一条线的有多少个。对于每个点的情况，取它所能覆盖的最大点个数。

　　在具体的实现中，有若干种情况需要考虑。对于一个点来说，可能有其他的点和它是在同一个点上，这个时候我们需要一个元素来计算它重复出现的个数。另外，对于和某个点在一条线上的元素，可能是在水平的x轴或者y轴上。还有的就是其他可能的情况。那么要判断其他的情况，我们可以通过计算平面上两个点之间的斜率来统计。

　　这样，我们可以通过在每访问一个点的时候建立一个Map<Double, Integer>，map里key表示从该点到另外一个节点的斜率，value表示这个斜率下的元素个数。而对于在垂直线上的元素来说，它相当于斜率是无穷大，我们可以用Double.MAX_VALUE来表示。每次我们碰到一个元素，就计算它的斜率并加入到map中。

　　详细的代码实现如下：

 

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if(points.length <= 1) return points.length;
        int max = 0;
        for(int i = 0; i < points.length; i++) {
            Map<Double, Integer> map = new HashMap<>();
            int duplicate = 1;
            for(int j = 0; j < points.length; j++) {
                if(i == j) continue;
                if(points[i].x == points[j].x && points[i].y == points[j].y) duplicate++;
                else if(points[i].y == points[j].y) map.put(Double.MAX_VALUE, map.containsKey(Double.MAX_VALUE) ? map.get(Double.MAX_VALUE) + 1 : 1);
                else {
                    double slope = 1.0 * (points[j].y - points[i].y) / (points[j].x - points[i].x);
                    map.put(slope, map.containsKey(slope) ? map.get(slope) + 1 : 1);
                }
            }
            if(map.isEmpty()) max = Math.max(max, duplicate);
            else {
                for(double d : map.keySet()) max = Math.max(max, map.get(d) + duplicate);
            }
        }
        return max;
    }
}