Max Points on a Line 解题报告

Max Points on a Line　解题报告

http://oj.leetcode.com/problems/max-points-on-a-line/

给你一组点，求共线最多点的个数。

思路，暴力枚举，以每个“点”为中心，然后遍历剩余点，求出以i为起点j为终点的斜率（j>i），斜率相同的点一定共线。

对每个i，初始化一个哈希表，key 为斜率，value 为该直线上的点数。遍历结束后得到和当前i点共线的点的最大值，再和全局最大值比较，最后就是结果。

时间复杂度O(n2)，空间复杂度O(n)。

其中有几点要注意的是： 存在坐标一样的点；存在斜率不存在的点（与x轴平行的直线）。

上AC代码：

[java] view plaincopy

1. public static int maxPoints(Point[] points) {  
2.       
3.     if(points.length<=2) {  
4.         return points.length;  
5.     }  
6.     //斜率  
7.     double k = 0.0;  
8.     int maxPointNum      = 0;  
9.     int tempMaxPointNum  = 0;  
10.     //坐标完全相同点的个数  
11.     int samePointNum     = 0;  
12.     //与x轴平行  
13.     int parallelPointNum = 0;   
14.     HashMap<Double,Integer> slopeMap = new HashMap<Double,Integer>();  
15.     for(int i=0;i<points.length-1;i++) {  
16.         //代表起始点，会被累加上  
17.         samePointNum     = 1;  
18.         parallelPointNum = 0;   
19.         tempMaxPointNum  = 0;  
20.         slopeMap.clear();  
21.         for(int j=i+1;j<points.length;j++) {  
22.             //坐标完全相同  
23.             if((points[i].x == points[j].x)&&((points[i].y == points[j].y))) {  
24.                 samePointNum++;  
25.                 continue;  
26.             }  
27.             //与x轴平行  
28.             if(points[i].x == points[j].x) {  
29.                 parallelPointNum++;  
30.             } else {  
31.                 if(points[i].y == points[j].y) {  
32.                     k = 0;  
33.                 } else {  
34.                     k = ((double)(points[i].y - points[j].y))/(points[i].x - points[j].x);  
35.                 }  
36.                 //斜率不存在  
37.                 if(slopeMap.get(k)==null) {  
38.                     slopeMap.put(k, new Integer(1));  
39.                     if(1>tempMaxPointNum) {  
40.                         tempMaxPointNum = 1;  
41.                     }  
42.                 }else {  
43.                     //斜率已存在  
44.                     int number = slopeMap.get(k);  
45.                     number++;  
46.                     slopeMap.put(k, new Integer(number));  
47.                     if(number>tempMaxPointNum) {  
48.                         tempMaxPointNum = number;  
49.                     }  
50.                 }  
51.             }  
52.         } //end of for  
53.           
54.         if(parallelPointNum>1) {  
55.             if(parallelPointNum>tempMaxPointNum) {  
56.                 tempMaxPointNum = parallelPointNum;  
57.             }  
58.         }  
59.         //加上起始点和具有相同坐标的点  
60.         tempMaxPointNum += samePointNum;  
61.         if(tempMaxPointNum>maxPointNum) {  
62.             maxPointNum = tempMaxPointNum;  
63.         }  
64.     }  
65.     return maxPointNum;  
66. }  

在上几个测试用例：

[java] view plaincopy

1. //Point[] array = { new Point(0,0)};  
2. //Point[] array = { new Point(0,0), new Point(0,0),new Point(0,0), new Point(0,0)};  
3. //Point[] array = { new Point(84,250), new Point(0,0) , new Point(1,0), new Point(0,-70), new Point(0,-70), new Point(1,-1), new Point(21,10), new Point(42,90),new Point(-42,-230)};  
4. //Point[] array = { new Point(0,0), new Point(0,1)};  
5. //Point[] array = { new Point(0,0), new Point(1,0)};  
6. //Point[] array = { new Point(1,1), new Point(1,2), new Point(1,3)};  
7. //Point[] array = { new Point(0,0), new Point(0,1), new Point(0,0)};  
8. //Point[] array = { new Point(2,3), new Point(3,3),new Point(-5,3)};  
9. Point[] array = {new Point(40,-23),new Point(9,138),new Point(429,115),new Point(50,-17),new Point(-3,80),new Point(-10,33),new Point(5,-21),new Point(-3,80),new Point(-6,-65),new Point(-18,26),new Point(-6,-65),new Point(5,72),new Point(0,77),new Point(-9,86),new Point(10,-2),new Point(-8,85),new Point(21,130),new Point(18,-6),new Point(-18,26),new Point(-1,-15),new Point(10,-2),new Point(8,69),new Point(-4,63),new Point(0,3),new Point(-4,40),new Point(-7,84),new Point(-8,7),new Point(30,154),new Point(16,-5),new Point(6,90),new Point(18,-6),new Point(5,77),new Point(-4,77),new Point(7,-13),new Point(-1,-45),new Point(16,-5),new Point(-9,86),new Point(-16,11),new Point(-7,84),new Point(1,76),new Point(3,77),new Point(10,67),new Point(1,-37),new Point(-10,-81),new Point(4,-11),new Point(-20,13),new Point(-10,77),new Point(6,-17),new Point(-27,2),new Point(-10,-81),new Point(10,-1),new Point(-9,1),new Point(-8,43),new Point(2,2),new Point(2,-21),new Point(3,82),new Point(8,-1),new Point(10,-1),new Point(-9,1),new Point(-12,42),new Point(16,-5),new Point(-5,-61),new Point(20,-7),new Point(9,-35),new Point(10,6),new Point(12,106),new Point(5,-21),new Point(-5,82),new Point(6,71),new Point(-15,34),new Point(-10,87),new Point(-14,-12),new Point(12,106),new Point(-5,82),new Point(-46,-45),new Point(-4,63),new Point(16,-5),new Point(4,1),new Point(-3,-53),new Point(0,-17),new Point(9,98),new Point(-18,26),new Point(-9,86),new Point(2,77),new Point(-2,-49),new Point(1,76),new Point(-3,-38),new Point(-8,7),new Point(-17,-37),new Point(5,72),new Point(10,-37),new Point(-4,-57),new Point(-3,-53),new Point(3,74),new Point(-3,-11),new Point(-8,7),new Point(1,88),new Point(-12,42),new Point(1,-37),new Point(2,77),new Point(-6,77),new Point(5,72),new Point(-4,-57),new Point(-18,-33),new Point(-12,42),new Point(-9,86),new Point(2,77),new Point(-8,77),new Point(-3,77),new Point(9,-42),new Point(16,41),new Point(-29,-37),new Point(0,-41),new Point(-21,18),new Point(-27,-34),new Point(0,77),new Point(3,74),new Point(-7,-69),new Point(-21,18),new Point(27,146),new Point(-20,13),new Point(21,130),new Point(-6,-65),new Point(14,-4),new Point(0,3),new Point(9,-5),new Point(6,-29),new Point(-2,73),new Point(-1,-15),new Point(1,76),new Point(-4,77),new Point(6,-29)};  
10. //最后一个测试用例是leetCode上面最难AC的一个数据，正确答案应该是25，小伙伴们AC了吗？  
11. System.out.println(LeetcodeMaxPointsOnALine.maxPoints(array));