Java for LeetCode 149 Max Points on a Line

浏览数：71 / 时间：2015年06月08日

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

解题思路：

本题主要需要考虑到斜线的情况，可以分别计算出过points[i]直线最多含几个点，然后算出最大即可，由于计算points[i]的时候，前面的点都计算过了，所以不需要把前面的点考虑进去，所以问题可以转化为过points[i]的直线最大点的个数，解题思路是用一个HashMap储存斜率，遍历points[i]后面每个点，看看和points[i]的斜率是否出现过，这里有个问题，如何储存斜率，理想状况下，斜率应该用一个String表示，如(0,0)和(2，4)可以存储为"1k2"这样的类型，这会涉及到求最大公约数的问题，实现起来比较麻烦，实际上直接用double表示即可通过，这是因为((double)1/((double)Integer.MAX_VALUE-(double)Integer.MIN_VALUE))是能输出2.3283064370807974E-10的。因此，我们直接用double即可。

JAVA实现如下：

    public int maxPoints(Point[] points) {
		if (points.length <= 2)
			return points.length;
		int max = 2;
		for (int i = 0; i < points.length; i++) {
			int pointMax = 1, samePointCount = 0;
			HashMap<Double, Integer> slopeCount = new HashMap<Double, Integer>();
			Point origin = points[i];
			for (int j = i + 1; j < points.length; j++) {
				Point target = points[j];
				if (origin.x == target.x && origin.y == target.y) {
					samePointCount++;
					continue;
				}
				double k;
				if (origin.x == target.x)
					k = Float.POSITIVE_INFINITY;
				else if (origin.y == target.y)
					k = 0;
				else
					k = ((double) (origin.y - target.y))
							/ (double) (origin.x - target.x);
				if (slopeCount.containsKey(k))
					slopeCount.put(k, slopeCount.get(k) + 1);
				else
					slopeCount.put(k, 2);
				pointMax = Math.max(pointMax, slopeCount.get(k));
			}
			max = Math.max(max, pointMax + samePointCount);
		}
		return max;  
    }

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java for LeetCode 149 Max Points on a Line