# 149. 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:

``````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
``````

C++ 解法一：

``````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> m;
int duplicate = 1;
for (int j = i + 1; j < points.size(); ++j) {
if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
++duplicate; continue;
}
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int d = gcd(dx, dy);
++m[{dx / d, dy / d}];
}
res = max(res, duplicate);
for (auto it = m.begin(); it != m.end(); ++it) {
res = max(res, it->second + duplicate);
}
}
return res;
}
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
};
``````

Java 解法一：

``````class Solution {
public int maxPoints(int[][] points) {
int res = 0;
for (int i = 0; i < points.length; ++i) {
Map<Map<Integer, Integer>, Integer> m = new HashMap<>();
int duplicate = 1;
for (int j = i + 1; j < points.length; ++j) {
if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
++duplicate; continue;
}
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int d = gcd(dx, dy);
Map<Integer, Integer> t = new HashMap<>();
t.put(dx / d, dy / d);
m.put(t, m.getOrDefault(t, 0) + 1);
}
res = Math.max(res, duplicate);
for (Map.Entry<Map<Integer, Integer>, Integer> e : m.entrySet()) {
res = Math.max(res, e.getValue() + duplicate);
}
}
return res;
}
public int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
}
``````

C++ 解法二：

``````class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int res = 0;
for (int i = 0; i < points.size(); ++i) {
int duplicate = 1;
for (int j = i + 1; j < points.size(); ++j) {
int cnt = 0;
long long x1 = points[i][0], y1 = points[i][1];
long long x2 = points[j][0], y2 = points[j][1];
if (x1 == x2 && y1 == y2) {++duplicate; continue;}
for (int k = 0; k < points.size(); ++k) {
int x3 = points[k][0], y3 = points[k][1];
if (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3 == 0) {
++cnt;
}
}
res = max(res, cnt);
}
res = max(res, duplicate);
}
return res;
}
};
``````

Java 解法二：

``````class Solution {
public int maxPoints(int[][] points) {
int res = 0, n = points.length;
for (int i = 0; i < n; ++i) {
int duplicate = 1;
for (int j = i + 1; j < n; ++j) {
int cnt = 0;
long x1 = points[i][0], y1 = points[i][1];
long x2 = points[j][0], y2 = points[j][1];
if (x1 == x2 && y1 == y2) {++duplicate;continue;}
for (int k = 0; k < n; ++k) {
int x3 = points[k][0], y3 = points[k][1];
if (x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1 * y3 == 0) {
++cnt;
}
}
res = Math.max(res, cnt);
}
res = Math.max(res, duplicate);
}
return res;
}
}
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/149

Line Reflection

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

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

https://leetcode.com/problems/max-points-on-a-line/discuss/47113/A-java-solution-with-notes

https://leetcode.com/problems/max-points-on-a-line/discuss/47117/Sharing-my-simple-solution-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation