Hash
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
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public int maxPoints(int[][] points) {
Map<Double, List<Set<int[]>>> slopeToEdgeCountMap = new HashMap<>();
int maxEdgeCount = 1;
for (int i = 0; i < points.length; i++) {
int x = points[i][0], y = points[i][1];
for (int j = i + 1; j < points.length; j++) {
int xi = points[j][0], yi = points[j][1];
double slope = (yi - y) / ((double) xi - x);
List<Set<int[]>> pointSetList = slopeToEdgeCountMap.computeIfAbsent(slope, k -> new ArrayList<>());
boolean added = false;
for (Set<int[]> pointSet : pointSetList) {
if (pointSet.contains(points[i]) || pointSet.contains(points[j])) {
pointSet.add(points[i]);
pointSet.add(points[j]);
maxEdgeCount = Math.max(maxEdgeCount, pointSet.size());
added = true;
break;
}
}
if (!added) {
Set<int[]> pointSet = new HashSet<>();
pointSet.add(points[i]);
pointSet.add(points[j]);
pointSetList.add(pointSet);
maxEdgeCount = Math.max(maxEdgeCount, pointSet.size());
}
}
}
return maxEdgeCount;
}
}
|
注意斜率相同的直线不一定在同一条线上，因为它们可能是平行的关系。
Math
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
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public int maxPoints(int[][] points) {
int maxPoints = 0;
for (int i = 0; i < points.length; i++) {
Map<String, Integer> slopeToCountMap = new HashMap<>();
int maxPointsStartWithThisPoint = 0;
int duplicateWithThisPoint = 0;
for (int j = i + 1; j < points.length; j++) {
int yDiff = points[j][1] - points[i][1];
int xDiff = points[j][0] - points[i][0];
if (yDiff == 0 && xDiff == 0) {
duplicateWithThisPoint++;
continue;
}
int gcd = gcd(xDiff, yDiff);
String slope = yDiff / gcd + "/" + xDiff / gcd;
slopeToCountMap.put(slope, slopeToCountMap.getOrDefault(slope, 0) + 1);
maxPointsStartWithThisPoint = Math.max(maxPointsStartWithThisPoint, slopeToCountMap.get(slope));
}
maxPoints = Math.max(maxPoints, 1 + maxPointsStartWithThisPoint + duplicateWithThisPoint);
}
return maxPoints;
}
private int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
}
|
References
149. Max Points on a Line
详细通俗的思路分析，多解法