java - 找到位于二维平面中同一条直线上的最大点数

Question

“给定二维平面上的 n 个点，找出位于同一条直线上的最大点数。”来自 leetcode.com 的问题我正在尝试解决它但我无法通过所有测试例。

我想做的是:- 我正在使用一个 hashmap，它的键是角度 b/w 我通过斜率的 tan 倒数得到的点，我存储每个斜率的值最初的值该点的出现次数，然后递增。

我正在使用另一个 hashmap 来计算点的出现。

我没有得到像 (0,0),(1,0) 这样的点的正确答案，它应该返回 2 但它返回了 1。

我错过了什么？

我的代码是:

public class MaxPointsINLine {
    int max = 0;
    int same;

    public int maxPoints(Point[] points) {
        int max = 0;
        Map<Double, Integer> map = new HashMap<Double, Integer>();
        Map<Point, Integer> pointmap = new HashMap<Point, Integer>();
        for(Point point: points)
        {
            if(!pointmap.containsKey(point))
            {
                pointmap.put(point, 1);
            }
            else
            {
                pointmap.put(point, pointmap.get(point)+1);
            }
        }
        if (points.length >= 2) {
            for (int i = 0; i < points.length; i++) {
                for (int j = i ; j < points.length; j++) {
                    double dx = points[j].x - points[i].x;
                    double dy = points[j].y - points[i].y;
                    double slope = Math.atan(dy / dx);
                    if (!map.containsKey(slope)) {
                        map.put(slope, pointmap.get(points[j]));
                    } else
                        map.put(slope, map.get(slope) + 1);
                }
            }
            for (Double key : map.keySet()) {
                if (map.get(key) > max) {
                    max = map.get(key);
                }
            }
            return max;
        } else if (points.length != 0) {
            return 1;
        } else {
            return 0;
        }
    } 

    public static void main(String[] args) {
        Point point1 = new Point(0,0);
        Point point2 = new Point(0,0);
        //Point point3 = new Point(2,2);
        MaxPointsINLine maxpoint = new MaxPointsINLine();
        Point[] points = { point1, point2};
        System.out.println(maxpoint.maxPoints(points));

    }

}

class Point {
    int x;
    int y;

    Point() {
        x = 0;
        y = 0;
    }

    Point(int a, int b) {
        x = a;
        y = b;
    }

    @Override
    public boolean equals(Object obj) {
        Point that = (Point)obj;
        if (that.x == this.x && that.y == this.y)
            return true;
        else
            return false;
    }

    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return 1;
    }
}

Answer 1

一般策略似乎行不通。假设我们已经成功地使用键值对 (a, N) 填充了 map，其中 a 是一个角度，N 是由角度 a 连接的点对的数量。考虑以下 6 个点的排列:

**
  **
**

明确地，点位于 (0,0)、(1,0)、(2,1)、(3,1)、(0,2) 和 (1,2)。您可以检查任何直线上的最大点数是否为 2。但是，有 3 对点以相同的角度连接:((0,0), (1,0)), ((2 ,1)、(3,1)) 和 ((0,2)、(1,2))。所以 map 将包含 N = 3 的键值对，但这不是原始问题的答案。

由于像上面这样的安排，仅仅计算坡度是不够的。成功的算法必须以能够区分平行线的方式表示线。