Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution:O(n*n)
public class Solution { public int maxPoints(Point[] points) {
Map<Double, Integer> map = new HashMap<>();
int ret = 0;
int size = points.length;
for (int i = 0; i < size; i++) {
int invalidK = 0;
int add = 1;
for (int j = i + 1; j < size; j++) {
if (points[j].x == points[i].x) {
if (points[j].y == points[i].y) {
add++;
} else {
invalidK++;
}
continue;
}
double slope = points[j].y == points[i].y ? 0.0: (1.0 * (points[j].y - points[i].y))/ (points[j].x - points[i].x); if (map.containsKey(slope)) {
int count = map.get(slope); map.put(slope, count + 1); } else { map.put(slope, 1); }
}
for (Integer it : map.values()) {
ret = Math.max(it.intValue() + add, ret);
}
ret = Math.max(invalidK + add, ret);
map.clear();
} return ret;
} }
沒有留言:
張貼留言