0%

[Leetcode]149. Max Points on a Line(C++)

题目描述

题目链接: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.

例子

例子 1

Input: [[1,1],[2,2],[3,3]]
Output: 3

例子 2

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

解题思路

解这道题一个简单的思路是通过两两遍历所有点对,并构造对应直线方程。通过哈系表存储所有可能直线包含的点的下标(不能是坐标因为可能有重合点),最后取包含点的最多的直线方程(中包含点的个数)即可。定义一条直线方程需要两个参数(斜率和截距),所以需要用二维哈希表。代码如下:

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
29
30
31
32
33
34
35
36
37
38
#include <vector>
#include <unordered_map>
#include <unordered_set>

class Solution {
public:
int maxPoints(std::vector<std::vector<int>>& points) {

if (points.size() < 3) return points.size();

std::unordered_map<long double, std::unordered_map<long double, std::unordered_set<int>>> line_points;
std::unordered_map<long double, std::unordered_set<int>> vertical_points;
int curMax = 0;

for (int i = 0; i < points.size(); i++) {
for (int j = i + 1; j < points.size(); j++) {
long double x1 = points[i][0], y1 = points[i][1];
long double x2 = points[j][0], y2 = points[j][1];

if (x1 == x2) { // x1 == x2, its on vertical line
vertical_points[x1].insert(i);
vertical_points[x1].insert(j);
curMax = std::max((int)vertical_points[points[i][0]].size(), curMax);
continue;
}

long double slope = (y1 - y2) / (x1 - x2);
long double offset = y1 - slope * x1;
line_points[slope][offset].insert(i);
line_points[slope][offset].insert(j);
curMax = std::max((int)line_points[slope][offset].size(), curMax);

}
}

return curMax;
}
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 149.MaxPointsOnALine.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions