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.

基本思路：

题目的意思就是找到一条直线，让最多的点在这条直线上，那么利用数学中的斜率定义，如果两个点与另外一个的斜率相等，那么这两个点与另外一个点在同一条直线上。

下面用到求最大公约数，注意：一个正数和一个负数求最大公约数是没意义的。

	//通过斜率相等来求
	public int maxPoints(Point[] points)
	{
		int maxSum = 0;
		if(points==null||points.length==0)
			return 0;
		//如果只有一个点时
		if(points.length==1)
			return 1;
		//以一个点为基点，分别求出其余点与这个点之间斜率
		for(int i = 0;i<points.length;i++)
		{
			int samePoint = 0;
			Map<String, Integer> map = new HashMap<String, Integer>();
			int maxSumtmp = 0;
			for(int j = 0;j<points.length;j++)
			{
				if(i==j)
					continue;
				int x = points[j].x - points[i].x;
				int y = points[j].y - points[i].y;
				
				int tmp = gcd(Math.abs(x), Math.abs(y));
				//两个点是同一点
				if(tmp==0)
				{
					samePoint++;
					continue;
				}
				//我们的目标是表x变为正数，而当x变号了的话，为了保持斜率不变，那么y也应该变号
				//如x=-1，y=-1，那么变为x=1，y=1；x=-1，y=1，那么变为x=1,y=-1;
				//此时我们就保证了以后比较map中key值时的不变形,如x=-1，y=-1和x=1，y=1的斜率相等，那么我们应该设置key值也相等，都为(1,1)
				if(x<0)
				{
					x = -x;
					y = -y;
				}
				//如果x和y中有一个为0，那么说明他们与x轴或y轴平行，那么斜率不存在正负
				if(x==0||y==0)
				{
					x = Math.abs(x);
					y = Math.abs(y);
				}
				String str = "("+(x/tmp)+","+(y/tmp)+")";
				if(map.keySet().contains(str))
					map.put(str, map.get(str)+1);
				else
					map.put(str, 1);
				maxSumtmp = maxSumtmp>map.get(str)?maxSumtmp:map.get(str);
			}
			maxSum = Math.max(maxSumtmp+1+samePoint, maxSum);
		}
		
		return maxSum;
	}
	
	//最大公约数,如果最大公约数为0 ，说明这两个数为均为0
	public int gcd(int a , int b)
	{
		return a==0?b:gcd(b%a, a);
	}

Max Points on a Line,布布扣,bubuko.com

Max Points on a Line

原文：http://blog.csdn.net/cow__sky/article/details/21740653