classSolution{ publicintmaxPoints(int[][] points){ if (points == null) return0; if (points.length <= 2) return points.length;
Map<Integer, Map<Integer, Integer>> map = new HashMap<Integer, Map<Integer, Integer>>(); int result = 0; for (int i = 0; i < points.length; i++) { map.clear(); int num = 1, max = 0; for (int j = i + 1; j < points.length; j++) { int x = points[j][0] - points[i][0]; int y = points[j][1] - points[i][1]; if (x == 0 && y == 0) { num++; continue; } int gcd = generateGCD(x, y); if (gcd != 0) { x /= gcd; y /= gcd; }
if (map.containsKey(x)) { map.get(x).put(y, map.get(x).getOrDefault(y, 0) + 1); } else{ Map<Integer, Integer> m = new HashMap<Integer, Integer>(); m.put(y, 1); map.put(x, m); } max = Math.max(max, map.get(x).get(y)); } result = Math.max(result, max + num); } return result; }
privateintgenerateGCD(int a, int b){ if (b == 0) return a; elsereturn generateGCD(b, a % b); } }
Solution 2
O(n^3), used Cross product to determine if these three points are in one line