Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2:
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
-
Method 1: I first used the double to calculate the slope but cause precision error. O(n^3) cannot AC.
class Solution { public int maxPoints(int[][] points) { int len = points.length; if(len <= 2) return len; int res = 0; for(int i = 0; i < len; i++){ for(int j = i + 1; j < len; j++){ int temp = 2; double x1 = (double)points[i][0]; double x2 = (double)points[j][0]; if(x1 != x2){ double y1 = (double)points[i][1]; double y2 = (double)points[j][1]; double s = (y2 - y1) / (x2 - x1); double b = y1 - s * x1; for(int k = 0; k < len; k++){ if(k == i || k == j) continue; double x = (double)points[k][0]; double y = (double)points[k][1]; if(y == x * s + b) temp++; } }else{ for(int k = 0; k < len; k++){ if(k == i || k == j) continue; double x = (double)points[k][0]; if(x == x1) temp++; } } res = Math.max(res, temp); } } return res; } }
-
Method 2: HashMap to save the slope(use string) AC
class Solution { public int maxPoints(int[][] points) { int len = points.length; if(len <= 2) return len; int res = 0; for(int i = 0; i < len; i++){ for(int j = i + 1; j < len; j++){ int temp = 2; double x1 = (double)points[i][0]; double x2 = (double)points[j][0]; if(x1 != x2){ double y1 = (double)points[i][1]; double y2 = (double)points[j][1]; double s = (y2 - y1) / (x2 - x1); double b = y1 - s * x1; for(int k = 0; k < len; k++){ if(k == i || k == j) continue; double x = (double)points[k][0]; double y = (double)points[k][1]; if(y == x * s + b) temp++; } }else{ for(int k = 0; k < len; k++){ if(k == i || k == j) continue; double x = (double)points[k][0]; if(x == x1) temp++; } } res = Math.max(res, temp); } } return res; } }
- Method 1: HashMap + slope
class Solution { private static final String inf = "inf"; public int maxPoints(int[][] points) { int len = points.length; if(len <= 2) return len; int res = 0; for(int i = 0; i < len; i++){ int[] a = points[i]; Map<String, Integer> map = new HashMap<>(); int base = 1, max = 0; for(int j = i + 1; j < len; j++){ int[] b = points[j]; if(a[0] == b[0] && a[1] == b[1]){ base++; continue; }else{ String slope = ""; if(a[0] == b[0]){//same straight line, slope = inf map.put(inf, map.getOrDefault(inf, 0) + 1); slope = inf; }else{ int gcd = gcd(a[1] - b[1], a[0] - b[0]); slope = (a[1] - b[1]) / gcd + "_" + (a[0] - b[0]) / gcd; map.put(slope, map.getOrDefault(slope, 0) + 1); } max = Math.max(max, map.get(slope)); } } res = Math.max(res, base + max); } return res; } private int gcd(int a, int b){ return b == 0 ? a: gcd(b, a % b); } }