Max Points on a Line

 1 import java.util.HashMap;
 2 import java.util.Iterator;
 3 
 4 public class Solution {
 5     public int maxPoints(Point[] points) {
 6         int maxNums = 0;
 7         HashMap<Float, Integer> kAndLineNum = new HashMap<Float, Integer>();
 8         kAndLineNum.put(Float.MAX_VALUE, 0);
 9         int duplicate = 1;
10         
11         for(int i = 0; i < points.length; i++){
12             kAndLineNum.clear();
13             duplicate = 1;
14             kAndLineNum.put(Float.MAX_VALUE, 0);
15             
16             for(int j = 0; j < points.length; j++){
17                 if(i == j)                        //
18                     continue;
19                 if(points[i].x == points[j].x && points[i].y == points[j].y){                //重复点
20                     duplicate ++;
21                     continue;
22                 }
23                 float k = 0;
24                 k = points[i].x == points[j].x ? Float.MAX_VALUE : (float)(points[i].y - points[j].y) / (points[i].x - points[j].x);    //计算斜率
25                 if(kAndLineNum.get(k) != null){                                                //和其他点在同一直线上
26                     Integer tempLineNum = kAndLineNum.get(k);
27                     tempLineNum ++;
28                     kAndLineNum.put(k, tempLineNum);
29                 }//if
30                 else{                                                                        //和其他点不在同意直线上
31                     kAndLineNum.put(k, 1);
32                 }//else
33             }//for
34             
35             for(Iterator<Float> iterator = kAndLineNum.keySet().iterator(); iterator.hasNext();){
36                 Float kValue = iterator.next();
37                 int pointsNum = kAndLineNum.get(kValue);
38                 maxNums = maxNums > (pointsNum + duplicate) ? maxNums : (pointsNum + duplicate);
39             }//for
40         }//for
41         
42         return maxNums;
43     }
44 }