149. Max Points on a Line 发表于 2022-08-23 Hash123456789101112131415161718192021222324252627282930313233343536class Solution { public int maxPoints(int[][] points) { Map<Double, List<Set<int[]>>> slopeToEdgeCountMap = new HashMap<>(); int maxEdgeCount = 1; // 题目判定时单个点也算作一条直线 for (int i = 0; i < points.length; i++) { int x = points[i][0], y = points[i][1]; for (int j = i + 1; j < points.length; j++) { int xi = points[j][0], yi = points[j][1]; double slope = (yi - y) / ((double) xi - x); List<Set<int[]>> pointSetList = slopeToEdgeCountMap.computeIfAbsent(slope, k -> new ArrayList<>()); boolean added = false; for (Set<int[]> pointSet : pointSetList) { if (pointSet.contains(points[i]) || pointSet.contains(points[j])) { pointSet.add(points[i]); pointSet.add(points[j]); maxEdgeCount = Math.max(maxEdgeCount, pointSet.size()); added = true; break; } } if (!added) { Set<int[]> pointSet = new HashSet<>(); pointSet.add(points[i]); pointSet.add(points[j]); pointSetList.add(pointSet); maxEdgeCount = Math.max(maxEdgeCount, pointSet.size()); } } } return maxEdgeCount; }} 注意斜率相同的直线不一定在同一条线上,因为它们可能是平行的关系。 Math12345678910111213141516171819202122232425262728293031323334353637class Solution { public int maxPoints(int[][] points) { int maxPoints = 0; for (int i = 0; i < points.length; i++) { Map<String, Integer> slopeToCountMap = new HashMap<>(); int maxPointsStartWithThisPoint = 0; int duplicateWithThisPoint = 0; for (int j = i + 1; j < points.length; j++) { int yDiff = points[j][1] - points[i][1]; int xDiff = points[j][0] - points[i][0]; if (yDiff == 0 && xDiff == 0) { duplicateWithThisPoint++; continue; } int gcd = gcd(xDiff, yDiff); String slope = yDiff / gcd + "/" + xDiff / gcd; slopeToCountMap.put(slope, slopeToCountMap.getOrDefault(slope, 0) + 1); maxPointsStartWithThisPoint = Math.max(maxPointsStartWithThisPoint, slopeToCountMap.get(slope)); } maxPoints = Math.max(maxPoints, 1 + maxPointsStartWithThisPoint + duplicateWithThisPoint); } return maxPoints; } private int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); }} Reference149. Max Points on a Line详细通俗的思路分析,多解法