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

这个“在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 map = new HashMap(); Map pointmap = new HashMap(); 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  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的键值对，但这不是原始问题的答案。

由于上述安排，计算斜坡是不够的。 成功的算法必须以这样的方式表示线条，以便您可以区分平行线。

Answer 2

这里最直接的解决方案似乎如下：可以考虑每对点。 对于每对，计算每个其他点到连接两个点的线的距离。 如果该距离几乎为零，则该点位于该线上。

当对所有对完成此操作时，可以选择连接线上具有最高点数的对。

当然，这不是很优雅，因为它在O（n ^ 2）中并执行两次计算。 但它非常简单而且非常可靠。 我刚刚在这里实现了这个MCVE ：

可以通过左键单击鼠标来设置点。 右键单击清除屏幕。 将显示一行中的最大点数，并突出显示相应的点。

（编辑：根据评论更新以处理距离为0的点）

 import java.awt.BorderLayout; import java.awt.Color; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.Point; import java.awt.event.MouseEvent; import java.awt.event.MouseListener; import java.awt.geom.Line2D; import java.util.ArrayList; import java.util.List; import javax.swing.JFrame; import javax.swing.JPanel; import javax.swing.SwingUtilities; public class PointsOnStraightLineTest { public static void main(String[] args) { SwingUtilities.invokeLater(new Runnable() { @Override public void run() { createAndShowGUI(); } }); } private static void createAndShowGUI() { JFrame f = new JFrame(); f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); f.getContentPane().setLayout(new BorderLayout()); f.getContentPane().add(new PointsPanel()); f.setSize(600, 600); f.setLocationRelativeTo(null); f.setVisible(true); } } class PointsOnStraightLine { // Large epsilon to make it easier to place // some points on one line with the mouse... private static final double EPSILON = 5.0; List maxPointsOnLine = new ArrayList(); void compute(List points) { maxPointsOnLine = new ArrayList(); for (int i=0; i resultPoints = null; if (p0.distanceSq(p1) < EPSILON) { resultPoints = computePointsNearby(p0, points); } else { resultPoints = computePointsOnLine(p0, p1, points); } if (resultPoints.size() > maxPointsOnLine.size()) { maxPointsOnLine = resultPoints; } } } } private List computePointsOnLine( Point p0, Point p1, List points) { List result = new ArrayList(); for (int k=0; k computePointsNearby( Point p0, List points) { List result = new ArrayList(); for (int k=0; k points; private final PointsOnStraightLine pointsOnStraightLine; PointsPanel() { addMouseListener(this); points = new ArrayList(); pointsOnStraightLine = new PointsOnStraightLine(); } @Override protected void paintComponent(Graphics gr) { super.paintComponent(gr); Graphics2D g = (Graphics2D)gr; g.setColor(Color.BLACK); for (Point p : points) { g.fillOval(px-2, py-2, 4, 4); } pointsOnStraightLine.compute(points); int n = pointsOnStraightLine.maxPointsOnLine.size(); g.drawString("maxPoints: "+n, 10, 20); g.setColor(Color.RED); for (Point p : pointsOnStraightLine.maxPointsOnLine) { g.drawOval(px-3, py-3, 6, 6); } } @Override public void mouseClicked(MouseEvent e) { if (SwingUtilities.isRightMouseButton(e)) { points.clear(); } else { points.add(e.getPoint()); } repaint(); } @Override public void mousePressed(MouseEvent e) { } @Override public void mouseReleased(MouseEvent e) { } @Override public void mouseEntered(MouseEvent e) { } @Override public void mouseExited(MouseEvent e) { } } 

Answer 3

这个对我有用：

 /** * 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) { int result = 0; for(int i = 0; i line = new HashMap(); Point a = points[i]; int same = 1; //System.out.println(a); for(int j = i+1; j