直线上最多的点数
题面
leetcode题目
给你一个数组 \(points\) ，其中 \(points[i] = [xi, yi]\) 表示 \(X-Y\) 平面上的一个点。求最多有多少个点在同一条直线上。
example-1
输入：\(points = [[1,1],[2,2],[3,3]]\)
输出：\(3\)
example-2
输入：\(points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]\)
输出：\(4\)
数据范围
- \(1 \leq points.length \leq 300\)
- \(points[i].length == 2\)
- \(-10^4 <= xi, yi <= 10^4\)
- \(points\) 中的所有点互不相同
题解
总体思路
对于在X-Y坐标系中的所有直线，都可表示为: \[ y = kx + b \tag{1}\] 如果已知两点\((x_1,y_1)\)和\((x_2,y_2)\)，其对应的直线参数\(k\)为: \[ k = \frac{\Delta y}{\Delta x} = \frac{y_2 - y_1}{x_2 - x_1} \tag{2}\] 将\((2)\)式带入\((1)\)式子，并带入任意一点即可求出\(b\)为:
\[ b = y - kx \] 很容易可以看出，在\(k\)一定的情况下，如果某一点确定，那么对于存在于其直线上的另外一点，求出的斜率\(k\)和截距\(b\)都是一定的，也就是说当\(k\)，\((x_1,y_1)\)确定的时候，对于任意\((x_i,y_i)\)，如果两点求斜率\(k_i = \frac{y_i - y_1}{x_i - x_1} = k\)，那么这三点一定在同一直线上。这也可以换个说法叫过某点斜率为\(k\)的直线有且只有一条。
在这些前提下我们再来考虑这道题，我们有一些点，需要求在同一 条直线上的点的数量，朴素的考虑我们可以枚举每一个点\(point_i\)，再来考虑没有重复的枚举点\(point_j\)，求枚举的\(point_j\)中在同一条直线上的点的数量即可。由上文我们可知，这实际上就是求对于\(point_i\)来讲，由多少个\(point_j\)与他构成的斜率\(k_j\)是一样的。我们只需要把斜率\(k_j\)用哈希表存起来，存储其出现的次数，那么结果就是其最大值。
斜率\(k\)可能是个小数，有精度问题，我们可以将他拆成一个字符串"\(\Delta y\)_\(\Delta x\)"来表示，由于分数的表示可能存在公约数的问题，我们需要求出其最简表示，对于负数问题我们只需要简单的约定只有分子能为负即可。
还存在两种特殊的情况: 斜率不存在与斜率为\(0\)。我们一个一个考虑。当斜率不存在时，其直线为一条垂直与\(x\)轴的直线，那么对于所有过\(point_i\)的斜率不存在的直线，有且只有一条，我们直接将斜率不存在的哈希key表示为一个特殊值即可。当斜率为\(0\)时候，对于\(+0\)和\(-0\)实际上都表示为平行于\(x\)轴的同一条直线，我们也将其哈希key表示为另一个特殊值即可解决这个问题。
!!! note Hexo-admonition 插件使用示例 这是基于 hexo-admonition 插件渲染的一条提示信息。类型为 note，并设置了自定义标题。
提示内容开头留 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;
#define _DEBUG
class Solution
{
public:
int maxPoints(vector<vector<int>> &points)
{
int len = points.size();
int ret = 1;
for (int i = 0; i < len; i++)
{
map<string, int> kmap;
auto point1 = points[i];
int x1 = point1[0];
int y1 = point1[1];
for (int j = i + 1; j < len; j++)
{
auto point2 = points[j];
int x2 = point2[0];
int y2 = point2[1];
int dx = x2 - x1;
int dy = y2 - y1;
if (dx < 0 && dy < 0)
{
dx *= -1;
dy *= -1;
}
if (dy < 0 && dx > 0)
{
dx *= -1;
dy *= -1;
}
int k = gcd(dx, dy);
int mx = dx / k;
int my = dy / k;
string hashKey = "";
if (my == 0)
{
hashKey = "DY";
}
else if (mx == 0)
{
hashKey = "DX";
}
else
{
hashKey = to_string(mx) + "_" + to_string(my);
}
#ifdef _DEBUG
cout << "x1: " << x1 << " x2: " << x2 << " y1: " << y1 << " y2: " << y2 << " dx:" << dx << " dy:" << dy << " k:" << k << " hashKey:" << hashKey << endl;
#endif
if (kmap.count(hashKey) == 0)
{
kmap[hashKey] = 0;
}
kmap[hashKey]++;
}
auto iter = kmap.begin();
while (iter != kmap.end())
{
int val = iter->second;
if (val + 1 > ret)
{
ret = val + 1;
}
iter++;
}
}
return ret;
}
int gcd(int x, int y)
{
if (x < 0)
{
return gcd(x * -1, y);
}
if (y < 0)
{
return gcd(x, y * -1);
}
#ifdef _DEBUG
cout << "x: " << x << " y: " << y << endl;
#endif
if (y > x)
{
return gcd(y, x);
}
if (y == 0)
{
return x;
}
return gcd(x - y, y);
}
};
int main()
{
Solution s;
vector<vector<int>> t4{
{2, 3},
{3, 3},
{-5, 3}};
cout << s.maxPoints(t4) << endl;
return 0;
}
|