05 August 2008
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
1
2
3
4
5
6
7
8
9
10
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2:
1
2
3
4
5
6
7
8
9
10
11
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
我们知道，两个点可以确定一条线。
因此一个朴素的做法是先枚举两条点（确定一条线），然后检查其余点是否落在该线中。
为了避免除法精度问题，当我们枚举两个点 ii 和 jj 时，不直接计算其对应直线的 斜率和 截距，而是通过判断 ii 和 jj 与第三个点 kk 形成的两条直线斜率是否相等（斜率相等的两条直线要么平行，要么重合，平行需要 44 个点来唯一确定，我们只有 33 个点，所以可以直接判定两直线重合）。
时间复杂度：O(n^3)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int maxPoints(int[][] ps) {
int len = ps.length;
int result = 1;
for (int i = 0; i < len; i++) {
int[] x = ps[i];
for (int j = i + 1; j < len; j++) {
int[] y = ps[j];
int cnt = 2;
for (int k = j + 1; k < len; k++) {
int[] p = ps[k];
int s1 = (y[1] - x[1]) * (p[0] - y[0]);
int s2 = (p[1] - y[1]) * (y[0] - x[0]);
if (s1 == s2) {
cnt++;
}
}
result = Math.max(result, cnt);
}
}
return result;
}
}
根据「朴素解法」的思路，枚举所有直线的过程不可避免，但统计点数的过程可以优化。
具体的，我们可以先枚举所有可能出现的 直线斜率（根据两点确定一条直线，即枚举所有的「点对」），使用「哈希表」统计所有 斜率 对应的点的数量，在所有值中取个 maxmax 即是答案。
一些细节：在使用「哈希表」进行保存时，为了避免精度问题，我们直接使用字符串进行保存，同时需要将 斜率 约干净。
时间复杂度：枚举所有直线的复杂度为 O(n^2)；令坐标值的最大差值为 mm，gcd 复杂度为 O(\log{m})O(logm)。整体复杂度为 O(n^2 * \log{m})
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int maxPoints(int[][] ps) {
int len = ps.length;
int result = 1;
for (int i = 0; i < len; i++) {
Map<String, Integer> map = new HashMap<>();
// 由当前点 i 发出的直线所经过的最多点数量
int max = 0;
for (int j = i + 1; j < len; j++) {
int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
int a = x1 - x2, b = y1 - y2;
int k = gcd(a, b);
String key = (a / k) + "_" + (b / k);
map.put(key, map.getOrDefault(key, 0) + 1);
max = Math.max(max, map.get(key));
}
result = Math.max(result, max + 1);
}
return result;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}