[leetcode]Max Points on a Line

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

坐标轴上面有n个点，求共线的最大点数。

这道题是leetcode上通过率最低的，但是绝对不是最难的，几点共线我们可以根据y = k x + b算出：

1. 平行于y轴的垂线斜率设为最大值，平行于x轴的线与普通斜线没啥区别，不需要做特殊处理；

2. 比较棘手的是重复点

这道题，我重构了一个数据结构，包含了k，b从而确定了每一条线，二重遍历坐标轴中每一个点（时间复杂度为n*n）从而遍历了图中的每一条线，但是当遇到重合点的时候，不知道该如何下手了。

后来查到了这样的算法，压根就不需要关心斜率，对每个点进行雷达式的扫描处理，简直碉堡。

其算法思想是这样的：

1. 对每个点p进行循环扫描（扫描坐标中所有的点），并维护一个duplicate变量，初值为1，表示自己。

2. 扫描到点q时，计算直线pq的斜率k，这时b就不需要关心了，原因自己画图，想一下就不难知道。

2.1 当p点与q点重合时，duplicate++

2.2 计算斜率（边界case，斜率为∞），记录斜率为k的直线个数

3. 对坐标中所有的点处理完之后，遍历map中的value + duplicate的最大值，有一种特殊情况：所有的点都是重合点，map为空。

 

代码如下：

	public int maxPoints(Point[] points) {
		if(points== null) return 0;
		if(points.length <= 2) return points.length;
		int max = 0;
		int duplicate = 1;//this field setting is amazing
		Map<Double,Integer> map = new HashMap<Double,Integer>();
		for(int i = 0; i < points.length; i++){
			map.clear();
			duplicate = 1;
			Point p = points[i];
			for(int j = 0 ; j < points.length; j++){
				if(i == j) continue;
				Point tem = points[j];
				double slope = 0.0;
				if(tem.x == p.x && tem.y == p.y){
					duplicate ++;
					continue;
				}else if(tem.x == p.x){
					slope = Integer.MAX_VALUE;
				}else{
					slope = tem.y == p.y ? 0 : 1.0 * (tem.y - p.y) / (tem.x - p.x);
				}
				map.put(slope, map.containsKey(slope) ? map.get(slope) + 1 : 1 );
			}
			if(map.keySet().size() == 0){
				max = duplicate;
			}
			for(double key : map.keySet()){
				max = Math.max(max, duplicate + map.get(key));
			}
			
		}
		return max;
	}