题目：
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
链接： http://leetcode.com/problems/max-points-on-a-line/
题解：
这道题是旧时代的残党，LeetCode大规模加新题之前的最后一题，新时代没有可以载你的船。要速度解决此题，之后继续刷新题。
主要思路是，对每一个点求其于其他点的斜率，放在一个HashMap中，每计算完一个点，尝试更新global max。
要注意的一些地方是 -
- 跳过当前点
- 处理重复
- 计算斜率的时候使用double
- 保存斜率时，第一次要保存2个点，并非1个
- 假如map.size() = 0， 这时尝试用比较max和 duplicate + 1来更新max
Time Complexity - O(n2)， Space Complexity - O(n)
/**
* 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) {
if(points == null || points.length == 0)
return 0;
HashMap<Double, Integer> map = new HashMap<>();
int max = 1; for(int i = 0; i < points.length; i++) { //for each point, find out slopes to other points
map.clear();
int duplicate = 0; //dealing with duplicates for(int j = 0; j < points.length; j++) {
if(j == i)
continue;
if(points[i].x == points[j].x && points[i].y == points[j].y) {
duplicate++;
continue;
} double slope = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x); if(map.containsKey(slope)) {
map.put(slope, map.get(slope) + 1);
} else
map.put(slope, 2);
} if(map.size() > 0) {
for(int localMax : map.values())
max = Math.max(max, localMax + duplicate);
} else
max = Math.max(max, duplicate + 1);
} return max;
}
}
二刷:
又做到了这一题。题目很短，很多东西没有说清楚。比如假如这n个点中有重复，这重复的点我们也要算在结果里。比如[0, 0][0, 0]这是两个点。
这回用的方法依然是双重循环，使用一个Map<Double, Integer>来记录每个点到其他点的斜率slope，然后每统计完一个点，我们尝试更新一下globalMax。这里有几点要注意:
- 有重复点的情况，这时候我们用一个整数dupPointNum来记录，并且跳过后面的运算
- 斜率
- 当点p1.x == p2.x时这时我们要设置slope = 0.0，否则map里可能会出现-0.0和0.0两个key
- 当点p1.y == p2.y的时候，我们要设置slope = Double.POSITIVE_INFINITY，否则map里可能出现Double.POSITIVE_INFINITY或者Double.NAGETIVE_INFINITY
- 其他情况我们可以使用直线的两点式方程算出斜率slope = (double)(p1.y - p2.y) / (p1.x - p2.x)
- 计算完一个点之后，我们遍历Map的value()集，跟globalMax比较，尝试更新
有意思的一点是Double.NaN虽然不等于Double.NaN，即(Double.NaN == Double.NaN)返回false。但作为map的key来说却能在查找时返回true，所以2.2也可以设置slope = Double.NaN.
Java:
Time Complexity - O(n2)， Space Complexity - O(n)
/**
* 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) {
if (points == null || points.length == 0) return 0;
Map<Double, Integer> map = new HashMap<>(points.length);
int max = 0, len = points.length; for (int i = 0; i < len; i++) {
map.clear();
int dupPointNum = 0;
for (int j = i + 1; j < len; j++) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
dupPointNum++;
continue;
}
double slope = 0.0;
if (points[j].y == points[i].y) slope = 0.0;
else if (points[j].x == points[i].x) slope = Double.POSITIVE_INFINITY;
else slope = (double)(points[j].y - points[i].y) / (points[j].x - points[i].x); if (map.containsKey(slope)) map.put(slope, map.get(slope) + 1);
else map.put(slope, 2);
}
max = Math.max(max, dupPointNum + 1);
for (int count : map.values()) max = Math.max(max, count + dupPointNum);
}
return max;
}
}
Update:
加入了排序去重，速度更快了一些。
/**
* 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) {
if (points == null || points.length == 0) return 0;
Arrays.sort(points, (Point p1, Point p2)-> (p1.x != p2.x) ? p1.x - p2.x : p1.y - p2.y);
Map<Double, Integer> map = new HashMap<>(points.length);
int max = 0, len = points.length; for (int i = 0; i < len; i++) {
if (i > 0 && points[i].x == points[i - 1].x && points[i].y == points[i - 1].y) continue;
map.clear();
int dupPointNum = 0;
for (int j = i + 1; j < len; j++) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
dupPointNum++;
continue;
}
double slope = 0.0;
if (points[j].y == points[i].y) slope = 0.0;
else if (points[j].x == points[i].x) slope = Double.POSITIVE_INFINITY;
else slope = (double)(points[j].y - points[i].y) / (points[j].x - points[i].x); if (map.containsKey(slope)) map.put(slope, map.get(slope) + 1);
else map.put(slope, 2);
}
max = Math.max(max, dupPointNum + 1);
for (int count : map.values()) max = Math.max(max, count + dupPointNum);
}
return max;
}
}
Reference：
https://leetcode.com/discuss/72457/java-27ms-solution-without-gcd
https://leetcode.com/discuss/57464/accepted-java-solution-easy-to-understand