Leetcode Max Points on a Line

Max Points on a Line

Total Accepted:3286Total Submissions:33373My Submissions

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

5星级难度题目。

本题是考对hash表的灵活运用，关键点：

1 斜率是double型的数据，和点对应起来那么hash表的容器就使用了unordered_map<double, int>；

2 要会排除同一位置的点，那一定是同一直线的点

3 要避免重复计算斜率，我这里的做法是增加一个hash容器，记录存在了的斜率，这样避免重复。

56ms左右的程序，本程序还是相当快的：

	int maxPoints(vector<Point> &points) 
	{
		if (points.size() < 3) return points.size();
		int repeat = countRepeat(0, points);
		if (repeat == points.size()) return repeat;

		unordered_map<double, int> mdi;
		unordered_map<double, int> marks;
		int mp = 2;

		for (int i = 0; i < points.size(); i++)
		{
			for (int j = i+1; j < points.size(); j++)
			{
				if (points[i].x == points[j].x && points[i].y == points[j].y) 
					continue;
				double a = points[j].x-points[i].x;
				double b = points[j].y-points[i].y;
				double k = a? b/a:(double)INT_MAX;
				if (!marks.count(k))
				{
					marks[k] = i+1;
					mdi[k] = repeat+1;
				}
				else if (marks[k] == i+1) mdi[k]++;
			}
			for (auto it:mdi) mp = max(mp, it.second);
			repeat = countRepeat(i+1, points);
			mdi.clear();
		}//for (int i...
		return mp;
	}

	int countRepeat(int i, vector<Point> &p)
	{
		int c = 1;
		for ( int j = i+1; j < p.size(); j++)
		{
			if (p[j].x == p[i].x && p[j].y == p[i].y) c++;
		}
		return c;
	}

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
const double INF = double(INT_MAX);
class Solution {
public:
	//2014-2-19 update
	int maxPoints(vector<Point> &points) 
	{
		unordered_map<double, int> ump_di1;
		unordered_map<double, int> ump_di2;
		int same_ps = samePoints(0, points);
		if (same_ps == points.size()) return same_ps;

		for (int i = 0; i < points.size(); i++)
		{
			for (int j = i+1; j < points.size(); j++)
			{
				if (isSame(points[i], points[j])) continue;
				double a = points[i].x - points[j].x;
				double b = points[i].y - points[j].y;
				double k = a == 0.0? INF : b/a;//a==0.0?不是a?
				if (ump_di1.count(k))
				{
					if (ump_di1[k] != i) continue;
				}
				else
				{
					ump_di1[k] = i;
					ump_di2[k] = same_ps;
				}
				ump_di2[k]++;
			}
			same_ps = samePoints(i+1, points);
		}
		int max_ps = 0;
		for (auto x:ump_di2)
			max_ps = max(max_ps, x.second);
		return max_ps;
	}
	int samePoints(int pos, vector<Point> &points)
	{
		int num = 1;
		for (int i = pos+1; i < points.size(); i++)
			if (isSame(points[pos], points[i]))
				num++;
		return num;
	}
	bool isSame(Point &a, Point &b)
	{
		return a.x == b.x && a.y == b.y;
	}
};