题目描述
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example1:
Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: ^ | | o | o | o +-------------> 0 1 2 3 4
Example1:
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.
解题思路
- 点共线，最主要的是斜率相等，我们可以使用一个map来存相应的k和这样的斜率有多少个
- 由于直接使用除法，可能精度是个问题，楼主的思想是使用最大公约数
- 参考
- 要让这两数分别除以它们的最大公约数，这样例如8和4，4和2，2和1，这三组商相同的数就都会存到一个映射里面，同样也能实现目标，而求 GCD 的函数如果用递归来写那么一行就搞定了
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int res = 0;
for(int i = 0; i < points.size(); i++){
map<pair<int,int>, int> mmap;
int duplicate = 1;
for(int j = i + 1; j < points.size(); j++){
if(points[j][0] == points[i][0] && points[j][1] == points[i][1]){
duplicate++;
continue;
}
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int d = gcd(dx, dy);
++mmap[{dx / d, dy / d}];
}
res = max(res, duplicate);
for(auto it = mmap.begin(); it != mmap.end(); it++){
res = max(res, it -> second + duplicate);
}
}
return res;
}
int gcd(int x, int y){
return y == 0 ? x : gcd(y, x % y);
}
};
