Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2:
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
SOLUTION
- 暴力解法,依次扫描每个点,对每个点都依次扫描其后面的所有点。只要斜率相同的就认为是在同一条直线上,用一个
Hashmap
来存储每个斜率和其出现的次数。找到最大的次数即可。 - 但需要处理几种特殊情况:
- 两个点重复,用一个
duplicate
变量记录重合的点。最后只需要和哈希表中的数字相加即为共线点的总数 - 垂直线 和 水平线
- 两个点重复,用一个
- 斜率:
dy/dx = (y2 -y1) / (x2 - x1)
, 即使用double也不一定准备,所以应该避免除法。- 把除数和被除数都保存下来,不做除法。
- 但是要让这两数分别除以它们的最大公约数,例如8和4,4和2,2和1,这三组商相同的数就都会存到一个映射里面。
- 求 GCD 的函数: 用递归, 经典解法
public int getGCD (int dy, int dx) {
return dx == 0 ? dy : getGCD (dx, dy % dx);
}
代码
class Solution {
public int maxPoints(int[][] points) {
if (points == null || points.length == 0 || points[0].length == 0) {
return 0;
}
// Map必须放在循环内,因为求的是基于每个点,对其以后的点求斜率,找斜率出现的最大值。如果放在外面,那么可能出现重复计算
// 比如[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]], 在计算【3,2】点的时候,后面【2,3】【4,1】,【1,4】都已经计算过了,斜率已经累加
// 如果不清零,那么当计算【2,3】点的时候,【2,3】【1,4】的斜率又会被累加一次,重复!
// Map<Map<Integer, Integer>, Integer> slopVsCount = new HashMap<> ();
int maxPoints = 0;
for (int i = 0; i < points.length; i++) {
Map<Map<Integer, Integer>, Integer> slopVsCount = new HashMap<> ();
int[] point1 = points[i];
int duplicate = 1;
int localMaxPoints = 0;
for (int j = i + 1; j < points.length; j++) {
int [] point2 = points [j];
if (point1[0] == point2[0] && point1[1] == point2[1]) {
duplicate ++;
} else {
Map<Integer, Integer> slope = getSlope (point1, point2);
int count = slopVsCount.getOrDefault (slope, 0);
count++;
// System.out.println (count);
slopVsCount.put (slope, count);
localMaxPoints = Math.max (localMaxPoints, count);
}
}
//System.out.println (localMaxPoints);
maxPoints = Math.max (maxPoints, localMaxPoints + duplicate);
}
return maxPoints;
}
public Map<Integer, Integer> getSlope (int[] point1, int[] point2) {
Map<Integer, Integer> result = new HashMap<> ();
int dy = point2[1] - point1[1];
int dx = point2[0] - point1[0];
// vertical line
if (dx == 0) {
result.put (0, point1[0]);
return result;
}
// horizontal line
if (dy == 0) {
result.put (point1[1], 0);
return result;
}
// for other slopes
int gcd = getGCD (dy, dx);
// System.out.println ("point1: " + point1[0] + " " + point1[1]);
// System.out.println ("point2: " + point2[0] + " " + point2[1]);
// System.out.println ("Slope --- dy: " + (dy / gcd) + " dx: " + (dx / gcd ));
result.put (dy / gcd, dx / gcd );
return result;
}
public int getGCD (int dy, int dx) {
return dx == 0 ? dy : getGCD (dx, dy % dx);
}
}
网友评论