首页 > 代码库 > 【leetcode】Max Points on a Line

【leetcode】Max Points on a Line

题目:给定二维坐标上的若干点,找出这样一条线,属于该线的点数最多,返回点数。

分析:两个点确定了一条直线。共线,说明斜率相同。那么确定一个点A,该点与其他的点就会生成不同的斜率。这些斜率中,会存在相同的,那么这些相同的斜率就说明他们跟A在同一条直线上。

这里我们把斜率分成两种,一种是正常的斜率,就是可以写成 y = kx + b形式的k;一种就是横坐标相同,纵坐标不相同的,这时的斜率为无穷大。

给定的点中,肯定会存在重复的点,我们把它称为称为“重数”(笔者临时起的名字,数学上不存在),那么以某个点为起点,计算出的斜率相同(共线)的点数时,要加上该点的重数。

最后,我们取以上两种斜率所确定的点中,点数最多的。

int maxPoints(vector<Point> &points) {

	int len = points.size();
	if(len < 1) 
		return 0;
	int maxPoint = 1;
	unordered_map<double, int> slops_map;
	
	for (int i = 0; i < len - 1; ++i)
	{
		slops_map.clear();
		//the number of points which just has the same x  coordinate
		int num_infinit = 1;
		//the same point as points[i].
		int num_same = 0;
		//most number of points which in the same normal slop line.
		int slop_max = 0x80000000;
		for (int j = i + 1; j < len; ++j)
		{
			//same points
			if(points[i].x == points[j].x && points[i].y == points[j].y)
			{
				num_same++;
				continue;
			}
			//vertical, which the slop is infinit.
			else if(points[i].x == points[j].x)
			     num_infinit++;
			
			// normal slop
			else 
			{
			    double cur_slop = (points[i].y - points[j].y)/(points[i].x - points[j].x + 0.0);
				if(slops_map.find(cur_slop) != slops_map.end())
					slops_map[cur_slop]++;
				else
					slops_map[cur_slop] = 2;
				if(slop_max < slops_map[cur_slop])
                    slop_max = slops_map[cur_slop];
		   	}
		}
	    maxPoint = max(max(num_infinit, slop_max + num_same), maxPoint);
	}
	return maxPoint;
}