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;
}