[leetcode] 149. Max Points on a Line

[leetcode] 149. Max Points on a Line

Description

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: 3Explanation:^|| o| o| o +------------->0 1 2 3 4

Example 2:

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

分析

题目的意思是：找到包含最多点的直线。 -核心是比较x和y除以最大公约数后的值，以此作为判断是否共线的依据。

代码

/** * Definition for a point. * 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& points) { int res=0; for(int i=0;i,int> m; int duplicate=1; for(int j=i+1;jsecond+duplicate); } } return res; } int gcd(int a,int b){ return b==0 ? a:gcd(b,a%b); }};

参考文献

​​[编程题]max-points-on-a-line​​​​[LeetCode] Max Points on a Line 共线点个数​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。