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
| // @Title: 直线上最多的点数 (Max Points on a Line)
// @Author: 15816537946@163.com
// @Date: 2019-09-03 23:33:20
// @Runtime: 8 ms
// @Memory: 3.7 MB
/*
* @lc app=leetcode.cn id=149 lang=golang
*
* [149] 直线上最多的点数
*
* https://leetcode-cn.com/problems/max-points-on-a-line/description/
*
* algorithms
* Hard (18.16%)
* Likes: 71
* Dislikes: 0
* Total Accepted: 4.3K
* Total Submissions: 23.8K
* Testcase Example: '[[1,1],[2,2],[3,3]]'
*
* 给定一个二维平面,平面上有 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
*
*/
func maxPoints(points [][]int) int {
result := 0
for i, p1 := range points {
sameP, sameX := 1, 0
slopeCounts := make(map[float64]int)
for j := 0; j < i; j++ {
p2 := points[j]
if p1[0] == p2[0] && p1[1] == p2[1] {
sameP++
} else if p1[0] == p2[0] {
sameX++
} else {
slope := float64(p1[1]-p2[1]) / float64(p1[0]-p2[0])
if _, exists := slopeCounts[slope]; exists {
slopeCounts[slope]++
} else {
slopeCounts[slope] = 1
}
}
}
result = int(math.Max(float64(result), float64(sameP+sameX)))
for _, count := range slopeCounts {
result = int(math.Max(float64(result), float64(count+sameP)))
}
}
return result
}
|