Java O(n^2) Solution


  • 0
    C

    Java O(n^2) Solution.

    O(n^2) enumrate every point and use a HashMap to save the slope of this points between the other points.

    All points in the same line share same slope.

    Slope can be represent by a Pair (dur_of_x / gcd , dur_of_y / gcd) to avoid double which may cause compute precision error.

    Be careful of the points with the same position.

    import java.util.*;
    import javafx.util.Pair;
    
    public class Solution {
    
        int n;
        int cnt = 0;
        Map<Pair<Integer,Integer>,Integer> mp ;
        List<Set<Integer>> lst;
    
        int gcd(int a,int b) {
            if(a==0) return b;
            return gcd(b%a,a);
        }
    
        public int maxPoints(Point[] points) {
    
            n = points.length;
            if(n==0) return 0;
            int mx=1;
    
            for(int i=0;i<n;i++) {
    
                mp = new HashMap<>();
                lst = new ArrayList<>();
                cnt = 0;
                int same = 0;
    
                for(int j=0;j<n;j++) {
    
                    if(i==j) continue;
    
                    int dx = points[i].x - points[j].x;
                    int dy = points[i].y - points[j].y;
    
                    if(dx==0&&dy==0) {
                        same ++;
                        continue;
                    }
    
                    int ddx = dx;
                    if(ddx<0) ddx=-ddx;
                    int ddy = dy;
                    if(ddy<0) ddy=-ddy;
    
                    int g = this.gcd(ddx, ddy);
    
                    dx = dx/g;
                    dy = dy/g;
    
                    if(dx<0&&dy<0) {
                        dx *= -1;
                        dy *= -1;
                    }
                    if(dx>0&&dy<0) {
                        dx *= -1;
                        dy *= -1;
                    }
    
                    int listid = mp.getOrDefault(new Pair(dx,dy),-1);
    
                    if(listid==-1) {
                        lst.add(new HashSet<Integer>());
                        mp.put(new Pair(dx,dy),cnt);
                        listid = cnt;
                        cnt++;
                    }
    
                    lst.get(listid).add(i);
                    lst.get(listid).add(j);
                }
    
                for(Pair<Integer,Integer> key : mp.keySet()) {
                    int listid = mp.get(key);
                    int inoneline = lst.get(listid).size();
                    if(mx<inoneline+same) {
                        mx = inoneline+same;
                    }
                }
                if(mx<same+1) {
                    mx = same+1;
                }
            }
    
            return mx;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.