题目描述
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2:
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
题意:给一堆二维平面上的点,求解最多有多少个点在同一条直线上。
算法1
(哈希表) $O(n^2)$
题解:首先我们知道任意两个不同的点就可以唯一确定一条直线。那么我们现在就枚举每一个点作为固定点,将剩下的点按照与该点的斜率划分不同的组。这里需要额外注意的地方是:重复点(我们使用duplicate计数),和固定点在同一条垂线上的点(我们使用vertical计数)。我们使用<string,int>
的哈希表来保存斜率与该斜率的其他点的个数。对于任意两个点的斜率$key = \frac{y_1 -y _2}{x_1 -x_2}$,我们将分子和分母进行约分后采取字符串的形式保存来避免精度问题。
class Solution {
public:
int gcd(int x,int y)
{
if(y == 0)
return x;
return gcd(y,x % y);
}
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if(n < 3) return n;
int res = 1;
for(int i = 0 ; i < n ; i ++)
{
int r = points[i][0],c = points[i][1];
unordered_map<string,int> hash;
int vertical = 0,duplicate = 0;
for(int j = i + 1 ; j < n ; j ++)
{
if(points[j][0] == points[i][0])
{
vertical ++;
if(points[j][1] == points[i][1])
duplicate ++;
}
}
for(int j = i + 1 ; j < n ; j ++)
{
if(points[j][0] != points[i][0])
{
int x = points[j][0],y = points[j][1],com = gcd(y - c,x - r);
string key = to_string( (y - c) / com) + "/" + to_string((x - r) / com);
hash[key] ++;
}
}
// 需要加上重复的点以及固定点
for(auto& it : hash)
res = max(res,it.second + duplicate + 1);
// 需要加上固定点
res = max(res,vertical + 1);
}
return res;
}
};
这里补充一个证明,就是对于相同的斜率,约分后的分子分母会是唯一的,比如两个点的斜率是
-5/3
,那么这条线上的点最后计算的结果都会是-5/3
而不会出现5/-3
,虽然它们在数学上是等价的都是 $-\frac{5}{3}$。这是由于在C++中取余操作里余数的符号与被除数的符号是相同的,所以
gcd(-a, -b) = gcd(-b, -a % -b) = gcd(-b, -(a % b))
,也就是说将a, b
同时取反后最后得到的最小公倍数也会是跟原来符号相反的,因此约分后会有相同的形式。为细心点赞
请问为啥约分后是唯一的? 我跑了下test case [[1, 1],[2,1],[2,2],[1,4],[3,3]], 发现key 里面会有1/-2
这里结果唯一是指
(-1, 2)
和(1, -2)
约分后的结果都是1/-2
,因为gcd(-1, 2) = -1
并且gcd(1, -2) = 1
。没错,我傻逼了…忽略我评论
再补充一点: $0 \% x = -1 \% -1 = -1 \% 1 = 1 \% -1 = 1 \% 1 = 0 (其中, x \neq 0)$,但是可以证明也不会有问题。