找到位于2D平面中同一直线上的最大点数

Question

这个"在2D平面上给定n个点,找到位于同一直线上的最大点数." 来自leetcode.com的问题我试图解决它,但我无法通过所有测试用例.

我想要做的是: - 我正在使用一个hashmap,其键是角度b/w,我通过斜率的tan反转得到的点,我存储的每个斜率的值最初是no的值发生这一点,然后递增它.

我正在使用另一个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

总体策略似乎行不通。假设我们已经成功填充了map键值对(a, N)，其中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))。Somap将包含一个键值对N = 3，但这不是原始问题的答案。

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