首页 > 代码库 > leetcode-[3]Max Points on a Line
leetcode-[3]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
思路：最多的点，必然是点连成线时，所有斜率相同的最多的组合情况；
那么如果不在同一直线点的组合也可能斜率相同，找其中一点与其它点连即可。
#include <iostream>#include <vector>#include <map>using namespace std;struct Point { int x; int y; Point(): x(0), y(0) {} Point(int a, int b): x(a), y(b) {}};class Solution {public: int maxPoints(vector<Point> &points) { if (points.size() < 2) return points.size(); int result = 0; for (int i = 0; i < points.size(); i++) { map<pair<int, int>, int> line; int overlap = 0, vertical = 0, curMax = 0; for (int j = i + 1; j < points.size(); j++) { if((points[i].x == points[j].x) && (points[i].y == points[j].y)) { overlap ++; continue; } else if (points[i].x == points[j].x) { vertical ++; } else { int dx = points[i].x - points[j].x; int dy = points[i].y - points[j].y; int gcd = GCD(dx, dy); dx /= gcd; dy /= gcd; line[make_pair(dx, dy)]++; curMax = max(line[make_pair(dx, dy)], curMax); } curMax = max(vertical, curMax); } result = max(result, curMax+overlap+1); } return result; } int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a%b); }};int main() { vector<Point> points; points.push_back(Point(3, 4)); points.push_back(Point(3, 4)); points.push_back(Point(3, 4)); Solution *solution = new Solution(); cout << solution->maxPoints(points) << endl; // (3,10),(0,2),(0,2),(3,10) vector<Point> points2; points2.push_back(Point(3, 10)); points2.push_back(Point(0, 2)); points2.push_back(Point(0, 2)); points2.push_back(Point(3, 10)); cout << solution->maxPoints(points2) << endl; return 0;}
leetcode-[3]Max Points on a Line
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。