Best Line: Given a two-dimensional graph with points on it, find a line which passes the most number of points.
Hints: #491, #520, #529, #563
解法
给你很多点，找一条线能够经过最多的点。
- 把点按照x排序
- 选第1个点
- 选第2个点和第1个点构成线，看经过多少个点
- 选第3个点和第1个点构成线，看经过多少个点
- 。。。
- 选第N个点
- 选第2个点
- 选第3个点和第2个点构成线，看经过多少个点
- 。。。
- 选第N个点和第2个点构成线，看经过多少个点
- 。。。
- 选第N-1个点
代码：
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
|
public class Point {
private double x;
private double y;
}
public interface Line {
boolean isCross(Point point);
}
public class NormalLine implements Line {
private double slope;
private double diff;
public boolean isCross(Point point) {
return point.x * slope + diff == point.y;
}
}
public class VerticalLine implements Line {
private double x;
public boolean isCross(Point point) {
return point.x == x;
}
}
private Line makeLine(Point p1, Point p2) {
if (p1.x == p2.x) {
return new VerticalLine(p1.x);
}
double slope = (p1.y - p2.y) / (p1.x - p2.x);
double diff = p1.y - p1.x * slope;
return new NormalLine(slope, diff);
}
public Line bestLine(Point[] points) {
int maxCross = 0;
Line bestLine = null;
for (int i = 0; i < points.length - 1; i++) {
for (int j = i + 1; j < points.length; j++) {
Line line = makeLine(points[i], points[j]);
currentCross = 2;
for (int k = j + 1; k < points.length; k++) {
if (line.isCross(points[k])) {
currentCross++;
}
}
if (currentCross > maxCross) {
bestLine = line;
maxCross = currentCross;
}
}
}
return bestLine;
}
|
时间复杂度：
在i层面，总共进行了N - 1次循环
在j层面，每次循环的次数为：N - 1、N - 2、。。。、2、1
在k层面，每次循环的次数为：N - 2，N - 3、。。。、2、1
所以复杂度为O(n3)，n为点的数量
解法2
弄一个Line的Map，记录每条Line的经过的点的数量。用两个循环只构造构造Line，遇到重复的Line则给这个Line的计数加1。最后选一个计数最大的Line。
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
|
public Line bestLine(Point[] points) {
Map<Line, Integer> lineCount = new HashMap<>();
for (int i = 0; i < points.length - 1; i++) {
for (int j = i + 1; j < points.length; j++) {
Line line = makeLine(points[i], points[j]);
Integer count = lineCount.get(line);
if (count == null) {
count = 1;
}
count++;
lineCount.put(line, count);
}
}
Line bestLine = null;
int max = 0;
for (Map.Entry<Line, Integer> entry : lineCount.entrySet()) {
Line line = entry.key();
int count = entry.value();
if (count > max) {
max = count;
bestLine = line;
}
}
return bestLine;
}
|
时间复杂度：O(N2)，N为点的数量
评论