[LeetCode]Max Points on a Line

对于每一个point p我们可以calculate其他任意一个point和p的斜率，如果有多个point和p连成的直线斜率相同，说明他们在一条直线上。所以我们需要一个map来记录所有point和p连成直线的斜率。那么我们用什么来做map的key呢，如果我们用double来表示斜率那么我们要用double做key，但是由于double精度的关系，两个几乎一样的数可能被map视为两个不同的key，从而map有可能无法准确储存我们想要的信息。所以我们另建一个struct用来表示分数，我们自己定义==和hash function。当然为了避免2/3和4/6被视为不同slope的情况，我们需要每一次找到分子和分母的最大公约数(gcd)，然后分子分母除以gcd保证其不可约分。对于斜率为0和无穷的情况我们用0/+-1和+-1/0来表示。除此之外，我们还要统计和当前point p重合的所有点，因为无论结果为何，这些点都会在结果集里，因为这一轮里所有的line都经过p。时间复杂度O(n^2)，代码如下：

	/**
	* Definition for a point.
	* struct Point {
	* int x;
	* int y;
	* Point() : x(0), y(0) {}
	* Point(int a, int b) : x(a), y(b) {}
	* };
	*/
	struct Fraction
	{
	long sign, above, below;
	Fraction(long numerator, long denominator)
	{
	sign = (numerator < 0) ^ (denominator < 0)? -1: 1;
	above = abs(numerator);
	below = abs(denominator);
	}
	};
	bool operator==(const Fraction& f1, const Fraction& f2)
	{
	return f1.sign == f2.sign && f1.above == f2.above && f1.below == f2.below;
	}
	struct hashFraction
	{
	size_t operator()(const Fraction& f) const
	{
	string sign = f.sign == 1? "": "-";
	string str = sign + to_string(f.above) + "/" + to_string(f.below);
	return std::hash<string>{}(str);
	}
	};
	class Solution {
	public:
	int maxPoints(vector<Point>& points) {
	int len = points.size(), res = 0;
	for(int i = 0; i < len; ++i)
	{
	unordered_map<Fraction, int, hashFraction> map;
	int dup = 1, currMax = 0;
	for(int j = 0; j < len; ++j)
	{
	if(j == i)continue;
	long y = (long)points[j].y - (long)points[i].y, x = (long)points[j].x - (long)points[i].x;
	if(!x && !y)
	++dup;
	else
	{
	long div = gcd(y, x);
	Fraction f(y / div, x / div);
	++map[f];
	currMax = max(currMax, map[f]);
	}
	}
	res = max(res, currMax + dup);
	}
	return res;
	}
	private:
	long gcd(long a, long b)
	{
	a = abs(a);
	b = abs(b);
	if(a < b)return gcd(b, a);
	if(!b)return a;
	return gcd(b, a % b);
	}
	};

view raw Max Points on a Line.cpp hosted with ❤ by GitHub