学步园

题目

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

给出n个点，判断在这些点中在同一直线最多的点，有几个？

思路

1 首先想到这的确可以用暴力破解来做。两点确定一条直线，那么每次找两个点，然后算其他点再这条直线上有几个，记录；最后最多的数量就是答案。可是这需要O(n^3)的时间复杂度，所以直接放弃代码，重新思考；

2 直线想到什么，公式y = kx +b 。只要有了公式，再确定一个点，那么就可以判断其他点在这条直线上否。可是要计算公式，仍然需要两个点啊。。。回到1的思路中去了。那么我们想想如果确定一个点，然后每个点A和它组合可以得到什么？发觉那些斜率相同的点，都在通过这个A的一条直线上。好，我们找到突破口了。

3 每次确定一个点A，记录所有其他点和A组合的斜率（HASHTABLE),斜率大小---出现次数。最后出现次数最多的就是通过A的直线上点最多的情况。然后遍历所有的点即可。

4 其中碰到几个细节：

a 如果和x轴垂直怎么办？斜率设为最大值。

b 斜率要用double或者float

c 如果和点A重复怎么办？应该算在这条直线上的，但是斜率会为0，那么我们另外设个变量，记录重复点。

d 每次都要clear hashtable，但如果一个点比较完，都是重复点，无法进行遍历hashtable怎么办？所以我们一定不能让hashtable为空，设个double最小值为0即可。

代码

public class Solution {
    public int maxPoints(Point[] points) {
       
		       if(points.length==0){
		            return 0;
		        }
		        if(points.length==1){
		            return 1;
		        }
		        int n = points.length;
		        int sum =2;
		        Map<Double,Integer> record = new HashMap<Double,Integer>();
		        for(int i =0;i<n;i++){
		            record.clear();
		            int duplicate =1;
		            record.put(Double.MIN_VALUE,0);
		            for(int j=0;j<n;j++){
		                if(i==j){
		                    continue;
		                }
		                if(points[i].x==points[j].x&&points[i].y==points[j].y){
		                    duplicate++;
		                    continue;
		                }
		                double k;
		                if(points[i].x==points[j].x){
		                    k = Integer.MAX_VALUE;
		                }
		                else{
		                    k=(double)(points[j].y-points[i].y)/(points[j].x-points[i].x);
		                }
		                if(record.containsKey(k)){
		                	record.put(k, record.get(k)+1);
		                }
		                else{
		                	record.put(k, 1);
		                }
		                
		            }
		            
		             for(Iterator<Integer> a = record.values().iterator();
		            		a.hasNext();){
		            	int temp = a.next();
		            	if(temp+duplicate>sum){
		            		sum = temp+duplicate;
		            	}
		            }
		            
		        }
		        return sum;
            
    }
}