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