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代碼:
- public static int maxPoints(Point[] points) {
-
- if(points.length<=2) {
- return points.length;
- }
-
- double k = 0.0;
- int maxPointNum = 0;
- int tempMaxPointNum = 0;
-
- int samePointNum = 0;
-
- int parallelPointNum = 0;
- HashMap<Double,Integer> slopeMap = new HashMap<Double,Integer>();
- for(int i=0;i<points.length-1;i++) {
-
- samePointNum = 1;
- parallelPointNum = 0;
- tempMaxPointNum = 0;
- slopeMap.clear();
- for(int j=i+1;j<points.length;j++) {
-
- if((points[i].x == points[j].x)&&((points[i].y == points[j].y))) {
- samePointNum++;
- continue;
- }
-
- if(points[i].x == points[j].x) {
- parallelPointNum++;
- } else {
- if(points[i].y == points[j].y) {
- k = 0;
- } else {
- k = ((double)(points[i].y - points[j].y))/(points[i].x - points[j].x);
- }
-
- if(slopeMap.get(k)==null) {
- slopeMap.put(k, new Integer(1));
- if(1>tempMaxPointNum) {
- tempMaxPointNum = 1;
- }
- }else {
-
- int number = slopeMap.get(k);
- number++;
- slopeMap.put(k, new Integer(number));
- if(number>tempMaxPointNum) {
- tempMaxPointNum = number;
- }
- }
- }
- }
-
- if(parallelPointNum>1) {
- if(parallelPointNum>tempMaxPointNum) {
- tempMaxPointNum = parallelPointNum;
- }
- }
-
- tempMaxPointNum += samePointNum;
- if(tempMaxPointNum>maxPointNum) {
- maxPointNum = tempMaxPointNum;
- }
- }
- return maxPointNum;
- }
在上幾個測試用例:
-
-
-
-
-
-
-
-
- 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)};
-
- System.out.println(LeetcodeMaxPointsOnALine.maxPoints(array));