149
Max Points on a Line
13.0%
Hard
不优化，直接数
数个数用HashMap
public class Solution {
public int maxPoints(Point[] points) {
if (points.length<=2) return points.length;
int max = 2;
for (int i=0;i<points.length;i++){
int sameCount=1, infCount=0, zeroCount = 0, otherLineCount = 0;
HashMap<Double, Integer> counter = new HashMap<Double, Integer>();
for (int j=i+1;j<points.length;j++){
if (points[i].x==points[j].x && points[i].y==points[j].y) sameCount++;
else if (points[i].x == points[j].x) infCount++;
else if (points[i].y == points[j].y) zeroCount++;
else{
Double k = (double)(points[j].y - points[i].y) / (points[j].x - points[i].x);
if (!counter.containsKey(k)) counter.put(k,1);
else counter.put(k, counter.get(k)+1);
otherLineCount = Math.max(otherLineCount, counter.get(k));
}
}
max = Math.max(max, otherLineCount + sameCount);
max = Math.max(max, infCount + sameCount);
max = Math.max(max, zeroCount + sameCount);
}
return max;
}
}
优化
