首页 > 代码库 > leetcode--Max Points on a Line

leetcode--Max Points on a Line

2024-07-06 23:01:46   235人阅读

Given n points on a 2D plane, find the maximum number of points that lie on the same straight 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
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
public class Solution {
    /**
     * This program is used to calculate the number of points on a line on a plane.
     * The algorithm is simple if there is no doubt on the definition of a line.
     * A line can be defined using a single point and slope, one can obtain the analytic expression.
     * So, the algorithm in the program is the following:
     * 1. For a fixed point, calculate the maximum number of points on the same line with the
     * fixed point.
     * 2. run a loop with respect to each point.
     *
     * @param points -- an array of points on plane
     * @return maximum number of points on a line
     * @author Averill Zheng
     * @version 2014-06-01
     * @since JDK 1.7
     */
     public int maxPoints(Point[] points) {
         int numberOfPoints = 0;
         int length = points.length;
         for(int i = 0; i < length; ++i){
             int max = maxPointsForFixedInterception(i, points);
             numberOfPoints = (numberOfPoints < max) ? max : numberOfPoints;
         }
         return numberOfPoints;
     }
      
     private int maxPointsForFixedInterception(int i, Point[] points){
         int max = 0, length = points.length;
         Map<Double, Integer> slope = new HashMap<Double, Integer>();
          
         if(length > 0){
             max = 1;
             if(length > 1){            
                 //on vertical line
                 int number = 1;
                 for(int j = 0; j < length; ++j){
                     if(j != i){
                         double x_coor = points[j].x - points[i].x;
                         double y_coor = points[j].y - points[i].y;
                         //on vertical-line
                         if(x_coor == 0 && y_coor != 0){
                             ++number;
                             max = (max < number)? number : max;
                         }
                         //repeat points
                         else if(x_coor == 0 && y_coor == 0){
                             ++max;
                         }
                         else{
                             double slopeValue = http://www.mamicode.com/y_coor / x_coor;
                             if(slope.containsKey(slopeValue)){
                                 int num = slope.get(slopeValue) + 1;
                                 max = (max < num) ? num : max;
                                 slope.put(slopeValue, num);
                             }
                             else{
                                 max = (max < 2) ? 2 : max;
                                 slope.put(slopeValue, 2);
                             }
                         }
                     }
                 }
             }
         }
         return max;
     }
}   

　　


联系
我们