题目:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
题解:
这道题就是给你一个2D平面,然后给你的数据结构是由横纵坐标表示的点,然后看哪条直线上的点最多。
(1)两点确定一条直线
(2)斜率相同的点落在一条直线上
(3)坐标相同的两个不同的点 算作2个点
利用HashMap,Key值存斜率,Value存此斜率下的点的个数。同时考虑特殊情况,如果恰巧遍历到一个相同坐标的点,那么就维护一个local的counter来记录相同的点。
维护一个localmax,计算当前情况下的最大值;再维护一个全局Max来计算总的最大值。
返回全局Max即可。
代码如下:
1 public int maxPoints(Point[] points) { 2 if(points.length == 0||points == null) 3 return 0; 4 5 if(points.length == 1) 6 return 1; 7 8 int max = 1; //the final max value, at least one 9 for(int i = 0; i < points.length; i++) { HashMap<Float, Integer> hm = new HashMap<Float, Integer>(); int same = 0; int localmax = 1; //the max value of current slope, at least one for(int j = 0; j < points.length; j++) { if(i == j) continue; if(points[i].x == points[j].x && points[i].y == points[j].y){ same++; continue; } float slope = ((float)(points[i].y - points[j].y))/(points[i].x - points[j].x); if(hm.containsKey(slope)) hm.put(slope, hm.get(slope) + 1); else hm.put(slope, 2); //two points form a line } for (Integer value : hm.values()) localmax = Math.max(localmax, value); localmax += same; max = Math.max(max, localmax); } return max; }
Reference:
http://blog.****.net/ttgump/article/details/23146357
http://blog.****.net/linhuanmars/article/details/21060933