Given n points on a 2D plane, find the maximum number of points that lie on the same straight 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 }