力扣296最佳碰头java

题目描述：

给定一个二维平面，平面上有n个点，求最多有多少点在同一条直线上。

示例:

输入： [[1,1],[2,2],[3,3]]
输出： 3
解释：
^
|
| o
| o
| o
+------------->
0 1 2 3 4

思路：

对于每个点i，用一个哈希表（dictionary）记录与i点的斜率，斜率相同的点在同一条直线上。对于每个点i，计算其与其它点的斜率，并记录斜率相同的点的个数，更新最大值即可。

需要注意以下几点：

- 对于重合的点，需要单独计数。
- 对于斜率不存在的点（即x坐标相等的点），需要单独计数。
- 对于斜率为0的点（即y坐标相等的点），需要单独计数。

代码实现：

class Solution {
public int maxPoints(int[][] points) {
if (points.length == 0) return 0;
if (points.length == 1) return 1;

int maxCount = 0;

for (int i = 0; i < points.length; i++) {
Map<Double, Integer> map = new HashMap<>();
int same = 1;
int vertical = 0;

for (int j = 0; j < points.length; j++) {
if (i == j) continue;

int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];

if (x1 == x2 && y1 == y2) {
same++;
} else if (x1 == x2) {
vertical++;
} else {
double k = (double)(y1 - y2) / (double)(x1 - x2);
map.put(k, map.getOrDefault(k, 1) + 1);
}
}

int count = vertical;
for (double k : map.keySet()) {
count = Math.max(count, map.get(k));
}
count += same;
maxCount = Math.max(maxCount, count);
}

return maxCount;
}
}

时间复杂度：O(n^2)