leetcode 149 直线上最多的点数

缘起

群里看有人水这道题目, 觉得挺有意思（困难tag）, 就做了 leetcode 149 直线上最多的点数

分析

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
给定一个二维平面，平面上有 n 个整点，求最多有多少个点在同一条直线上。

示例 1:

输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4
示例 2:

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

思路是 O(n^2) 算法. 遍历每个点, 对每个点去遍历其他点. 求出斜率. 注意, 因为给的都是整点, 所以对于两个点, 只需要求出gcd即可. 然后求出既约分数. 将既约分数作为hashmap的key存起来. 然后统计即可. 

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
class Solution {
typedef pair<int, int> P;
public:
	int maxPoints(vector<vector<int>>& points) 
	{
		n = points.size();
		if (!n)
		{
			return 0;
		}
		ans = 0;
		for (int i= 0;i<n; i++) // 每次统计和points[i]的斜率
		{
			m.clear(); // 每次都清空哈希表
			int d =  0, same = 0; // same是和points[i]坐标一样的点
			for (int j = 0; j<n; j++) // 考察 points[j]和points[i]的斜率
			{
				if (i==j)
				{
					continue;
				}
				if (points[j][0]==points[i][0] && points[j][1]==points[i][1])
				{
					++same;
					continue;
				} // same中的点可以是任何斜率
				d  = max(d, ++m[kk(points[i][0], points[i][1], points[j][0], points[j][1])]); // 斜率为某一个值的个数++
			}
			ans = max(ans, d+same);
		}
		return ++ans; // 要算上自己
	}

	int n, ans; // 点的个数
	map<P, int> m; // key是分母非负既约分数, value是点的个数

	P kk(int x, int y, int a, int b) // 求(x,y)和(a,b) 的既约分数, 保证该既约分数的分母>=0, 分母放在pair->second的位置
	{
		if (x<a)
		{
			swap(x,a);
			swap(y,b);
		} // 保证x-a>=0, 因为我们要求的是 (y-b)/(x-a) 这种既约分数
		if (x==a)
		{
			return b>y?P(1,0):P(-1,0);
		}
		int d = gcd(y-b,x-a);
		return P((y-b)/d,(x-a)/d);
	}

	int gcd(int a, int b) // 欧几里得求 gcd(b,a)
	{
		return b?gcd(b,a%b):a;
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
32 ms
, 在所有 cpp 提交中击败了
45.52%
的用户
内存消耗 :
12.4 MB
, 在所有 cpp 提交中击败了
12.32%
的用户

所以说, 其实并不是这题有多难~ 思路很好想, 但是细节太多, 容易wa