【leetcode】Max Points on a Line

地址

https://leetcode.com/problems/max-points-on-a-line/

题目

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

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4

Example 2:

1
2
3
4
5
6
7
8
9
10
11
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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

思路

直线可以用y=kx+b表示,<k,b>可以表示一条直线。如果我们求过点P的直线,那么只用斜率k就可以表示出来了,b可以不用管。

法一:我们可以用map<double, int>来求有多少个相同的k。但求斜率k=(y2-y1)/(x2-x1)时有浮点误差,直接比较不可行。注意到题目中所有点的坐标都是整数,所以斜率k=(y2-y1)/(x2-x1)可以化简成分数表示,将分子分母同除两者的gcd,则可以使用<ny,nx>来表示k。

法二:不使用map来统计,使用数组记录所有的k=(y2-y1)/(x2-x1)。然后对数组sort一遍,从左到右扫描一遍数组统计即可。统计时判断相等用abs(x-y) < eps来处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
map<pair<int,int>, int>hs;
int ans = 0;
for(int i = 0, n = points.size(); i < n; ++i)
{
hs.clear();
int cnt = 0, x, y, d, same=1;
for(int j = i + 1; j < n; ++j)
{
x = 0, y = 1e9;
if(points[i] == points[j])
{
same+=1;
continue;
}
d = __gcd(points[j][1] - points[i][1], points[j][0] - points[i][0]);
x = (points[j][1] - points[i][1]) / d;
y = (points[j][0] - points[i][0]) / d;
cnt = max(cnt, ++hs[make_pair(x,y)]);
//cout<<k<<" "<<hs[k]<<endl;
}
ans = max(ans, cnt+same);
}
return ans;
}
};