首页 > 代码库 > [CC150] Find a line passing the most number of points

[CC150] Find a line passing the most number of points

2024-07-06 07:33:02   222人阅读

Problem: Given a two-dimensional graph with points on it, find a line which passes the most number of points.

此题是Cracking the code 5th edition 第七章第六题，思路就是 n choose 2, 所以时间复杂度是O(n^2)，因为没有更快的办法。

此题的难点在于两点一线计算出的斜率是浮点型，不好比较equality。所以其中需要有一个精确到哪一位的概念，英文是 round to a given place value.

我认为此题书中给的解法特别傻逼，而且时间复杂度也超出了O(n^2)，故自己写了一个更好的版本。

另，关于使用自定义类用作HashMap的键值，如何重写equals()和hashCode()，下面的代码给出的很好的示范。

?
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
package chapter7;
 
import java.util.HashMap;
 
// given a two-dimensional graph with points on it,
// find a line which passes the most number of points
// Time: O(N^2), N is number of points
 
// The tricky part is checking the equality of slope
// which is of type double.
// My solution is floor all values to an epsilon value
// which specifies the desired precision
 
public class P6 {
     
    public Line findBestLine(GraphPoint[] points){
        Line bestLine = null;
        int bestCount = 0;
        HashMap<Line, Integer> lineCounts =
                new HashMap<Line, Integer>();
         
        for(int i = 0; i < points.length; ++i){
            for(int j = i+1; j < points.length; ++j){
                Line line = new Line(points[i], points[j]);
                int currentCount;
                 
                if(lineCounts.containsKey(line)){
                    currentCount = lineCounts.get(line) + 1;
                }else{
                    currentCount = 1;
                }
                lineCounts.put(line, currentCount);
                 
                if(currentCount > bestCount){
                    bestCount = currentCount;
                    bestLine = line;
                }
            }
        }
         
        return bestLine;
    }
}
 
 
class Line{
    // for precision
    // slope and intercept values are floored to epsilon
    public static double epsilon = .0001;
     
    // properties for a normal line
    public double slope;
    public double y_intercept;
     
    // properties for a verticle line
    public boolean infinite_slope = false;
    public double x_intercept;
     
    public Line(GraphPoint p1, GraphPoint p2){
         
        if(p1.x == p2.x){
            this.infinite_slope = true;
            this.x_intercept = p1.x;
             
        }else{
            this.slope = (p1.y - p2.y) / (p1.x - p2.x);
            this.y_intercept = p1.y - slope * p1.x;
         
        }
         
        // floor all properties
        this.slope = floor(this.slope);
        this.x_intercept = floor(this.x_intercept);
        this.y_intercept = floor(this.y_intercept);
    }
 
    public double floor(double val){
        int val2 = (int)(val / epsilon);
        return val2 * epsilon;
    }
     
    @Override
    public int hashCode(){
        if(infinite_slope){
            return (int) x_intercept;
        }else{
            return (int) (slope + y_intercept);
        }
    }
     
    @Override
    public boolean equals(Object obj){
        if(this == obj)
            return true;
        if(obj == null)
            return false;
        if(getClass() != obj.getClass())
            return false;
         
        Line other = (Line)obj;
         
        if(infinite_slope && other.infinite_slope){ // both true
            return x_intercept == other.x_intercept;
             
        }else if(infinite_slope || other.infinite_slope){ // one true, one false
            return false;
        }
        else{ // both false
            return slope == other.slope && y_intercept == other.y_intercept;
        }
    }
}
 
 
class GraphPoint{
    // assume that x and y are both floored
    // to some point
    public double x;
    public double y;
}

　　


联系
我们