Description
https://leetcode.com/problems/max-points-on-a-line/
給定平面内n個點,求同一直線上的點的最大個數。
Solving Ideas
https://blog.csdn.net/qq_32767041/article/details/88386459
https://leetcode.com/problems/max-points-on-a-line/discuss/47113/A-java-solution-with-notes
時間複雜度: O ( n 2 ) O(n^2) O(n2)
空間複雜度: O ( n ) O(n) O(n)
Solution
class Solution {
public int maxPoints(Point[] points) {
if (points == null) return 0;
if (points.length <= 2) return points.length;
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
int res = 0;
for (int i = 0; i < points.length; i++) {
int overlap = 0, count = 0;
for (int j = i + 1; j < points.length; j++) {
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
if (dx == 0 && dy == 0) {
overlap++;
continue;
}
int gcd = gcd(dx, dy);
dx /= gcd;
dy /= gcd;
if (map.containsKey(dx)) {
if (map.get(dx).containsKey(dy)) {
map.get(dx).put(dy, map.get(dx).get(dy) + 1);
} else {
map.get(dx).put(dy, 1);
}
} else {
Map<Integer, Integer> m = new HashMap<>();
m.put(dy, 1);
map.put(dx, m);
}
count = Math.max(count, map.get(dx).get(dy));
}
res = Math.max(res, count + 1 + overlap);
map.clear();
}
return res;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}