Leetcode Max Points on a Line

Max Points on a Line

 Total Accepted: 3286 Total Submissions: 33373My Submissions

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

本题是考对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;
	}








Leetcode Max Points on a Line

上一篇:UVa 424 整数查询


下一篇:Java必备:对象与垃圾回收