Java O(n^2) solution as reference


  • 0
    Z

    I did not use GCD because Java does not provide multiple keys hashmap. So I just use slope and go over all the points using for loop.

    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    import java.util.Map.Entry;
    
    public class Solution {
    	public int maxPoints(Point[] points) {
    		int maxValAll = 0;
    		for (int i = 0; i < points.length; i++){
    			Point pivot = points[i];
    			Map<Double, Integer> map = new HashMap<Double, Integer>();
    			double slope = 0;
    			int vertical = 0;
    			int ident = 1;
    			for (int j = i+1; j < points.length; j++){
    				if(points[j].x == pivot.x && points[j].y == pivot.y){
    					ident++;
    				} else if(points[j].x == pivot.x){
    					vertical++;
    				} else {
    					slope = getSlope(pivot, points[j]);
    					if(map.containsKey(slope)) {
    						Integer val = map.get(slope);
    						map.put(slope, val + 1);
    					} else {
    						map.put(slope, 1);
    					}
    				}
    			}
    			int maxVal = iterHashMap(map);
    			if(maxVal < vertical){
    				maxVal = vertical;
    			}
    			maxVal += ident;
    			if(maxValAll < maxVal){
    				maxValAll = maxVal;
    			}
    		}
    		return maxValAll;
    		
    	}
    	
    	public int iterHashMap(Map<Double, Integer> map){
    		Iterator<Entry<Double, Integer>> iter = map.entrySet().iterator(); 
    		int maxVal = 0;
    		while (iter.hasNext()) { 
    			Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>) iter.next(); 
    			int val = (int) entry.getValue(); 
    			if((int)val > maxVal){
    				maxVal = val;
    			}
    		} 
    		return maxVal;
    	}
    	
    	public double getSlope(Point a, Point b){
    		double slope = (a.y - b.y)*1.0/(a.x - b.x);
    		if(slope == 0){
    			return 0;
    		}
    		return slope;
    	}
    }

Log in to reply
 

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