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
| struct Solution;
// @lc code=start
impl Solution {
/// ## 解题思路
/// - hashmap
/// 1. 最多只有n个点都在一条直线上,
/// 2. 在一条直线上的点, 到其中一个点(x0,y0)的斜率相等.
/// 即(xi-x0)/(yi-y0)相等;
/// 3. 从一个点出发, 依次计算其他点与该点的斜率, 统计相同斜率最大的点数
/// 此时需要用到hashmap;
/// 4. 由于斜率为float类型, 为了保证严格相等, 用约分后的(dx, dy)来代替;
pub fn max_points(points: Vec<Vec<i32>>) -> i32 {
use std::collections::HashMap;
let n = points.len();
if n <= 2 {
return n as i32;
}
// 辗转相除法计算a, b最大公约数
fn gcd(a: i32, b: i32) -> i32 {
assert!(a != 0 && b != 0);
let (mut a, mut b) = (a.abs(), b.abs());
let (mut a, mut b) = if a > b { (a, b) } else { (b, a) };
while a % b != 0 {
let c = a % b;
if c > b {
a = c;
} else {
a = b;
b = c;
}
}
b
}
let mut max_count = 0;
for i in 0..n - 1 {
let mut lines = HashMap::new();
let (x1, y1) = (points[i][0], points[i][1]);
for j in i + 1..n {
let (x2, y2) = (points[j][0], points[j][1]);
let (dx, dy) = match (x1 - x2, y1 - y2) {
(0, _) => (0, 1),
(_, 0) => (1, 0),
_ => {
let (dx, dy) = (x1 - x2, y1 - y2);
let sig = if dx * dy > 0 { 1 } else { -1 };
let gcd = gcd(dx.abs(), dy.abs());
(sig * dx.abs() / gcd, dy.abs() / gcd)
}
};
let count = lines.entry((dx, dy)).or_insert(1);
*count += 1;
max_count = max_count.max(*count);
}
}
max_count
}
}
// @lc code=end
|
