|
1 | | -packagecom.fishercoder.solutions; |
| 1 | +**Updatedsolution** [credits](https://leetcode.com/problems/max-points-on-a-line/discuss/328269/A-Java-solution-with-my-understanding) |
2 | 2 |
|
3 | | -importcom.fishercoder.common.classes.Point; |
4 | | -importjava.util.HashMap; |
5 | | -importjava.util.Map; |
6 | | - |
7 | | -/** |
8 | | - * 149. Max Points on a Line |
9 | | - * |
10 | | - * Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. |
11 | | - * |
12 | | - * Example 1: |
13 | | - * Input: [[1,1],[2,2],[3,3]] |
14 | | - * Output: 3 |
15 | | - * Explanation: |
16 | | - * ^ |
17 | | - * | |
18 | | - * | o |
19 | | - * | o |
20 | | - * | o |
21 | | - * +-------------> |
22 | | - * 0 1 2 3 4 |
23 | | - * |
24 | | - * Example 2: |
25 | | - * Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] |
26 | | - * Output: 4 |
27 | | - * Explanation: |
28 | | - * ^ |
29 | | - * | |
30 | | - * | o |
31 | | - * | o o |
32 | | - * | o |
33 | | - * | o o |
34 | | - * +-------------------> |
35 | | - * 0 1 2 3 4 5 6 |
36 | | - * |
37 | | - */ |
38 | | -publicclass_149 { |
39 | | - |
40 | | -publicstaticclassSolution1 { |
41 | | -/** credit: https://leetcode.com/problems/max-points-on-a-line/discuss/47113/A-java-solution-with-notes */ |
42 | | -publicintmaxPoints(Point[]points) { |
43 | | -if (points ==null) { |
44 | | -return0; |
45 | | - } |
46 | | -if (points.length <=2) { |
47 | | -returnpoints.length; |
48 | | - } |
49 | | - |
50 | | -Map<Integer,Map<Integer,Integer>>map =newHashMap<>(); |
51 | | -intresult =0; |
52 | | -for (inti =0;i <points.length;i++) { |
53 | | -map.clear(); |
54 | | -intoverlap =0; |
| 3 | +classSolution { |
| 4 | +publicintmaxPoints(int[][]points) { |
| 5 | +if(points.length <3)returnpoints.length; |
55 | 6 | intmax =0; |
56 | | -for (intj =i +1;j <points.length;j++) { |
57 | | -intx =points[j].x -points[i].x; |
58 | | -inty =points[j].y -points[i].y; |
59 | | -if (x ==0 &&y ==0) { |
60 | | -overlap++; |
61 | | -continue; |
62 | | - } |
63 | | -intgcd =generateGCD(x,y); |
64 | | -if (gcd !=0) { |
65 | | -x /=gcd; |
66 | | -y /=gcd; |
67 | | - } |
68 | | - |
69 | | -if (map.containsKey(x)) { |
70 | | -if (map.get(x).containsKey(y)) { |
71 | | -map.get(x).put(y,map.get(x).get(y) +1); |
72 | | - }else { |
73 | | -map.get(x).put(y,1); |
| 7 | +HashMap<Long,Integer>map =newHashMap<Long,Integer>(); |
| 8 | +for(inti =0;i <points.length;i++) { |
| 9 | +intdup =1; |
| 10 | +map.clear(); |
| 11 | +for(intj =i +1;j <points.length;j++) { |
| 12 | +intdx =points[j][0] -points[i][0],dy =points[j][1] -points[i][1]; |
| 13 | +if(dx ==0 &&dy ==0)dup++; |
| 14 | +else { |
| 15 | +intgcd =getGcd(dx,dy); |
| 16 | +longslope = ((long)(dy /gcd) <<32) + (dx /gcd); |
| 17 | +map.put(slope,map.getOrDefault(slope,0) +1); |
| 18 | + } |
74 | 19 | } |
75 | | - }else { |
76 | | -Map<Integer,Integer>m =newHashMap<>(); |
77 | | -m.put(y,1); |
78 | | -map.put(x,m); |
79 | | - } |
80 | | -max =Math.max(max,map.get(x).get(y)); |
| 20 | +max =Math.max(max,dup); |
| 21 | +for(Map.Entry<Long,Integer>entry :map.entrySet()) |
| 22 | +max =Math.max(max,entry.getValue() +dup); |
81 | 23 | } |
82 | | -result =Math.max(result,max +overlap +1); |
83 | | - } |
84 | | -returnresult; |
| 24 | +returnmax; |
85 | 25 | } |
86 | | - |
87 | | -privateintgenerateGCD(inta,intb) { |
88 | | -if (b ==0) { |
89 | | -returna; |
90 | | - }else { |
91 | | -returngenerateGCD(b,a %b); |
92 | | - } |
| 26 | + |
| 27 | +intgetGcd(inta,intb) { |
| 28 | +returnb ==0 ?a :getGcd(b,a %b); |
93 | 29 | } |
94 | | - } |
95 | 30 | } |