lintcode Max Points on a Line

本是古典何须时尚 2022-07-15 13:19 123阅读 0赞

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Have you met this question in a real interview?

Yes

Example

Given 4 points: `(1,2)`, `(3,6)`, `(0,0)`, `(1,3)`.

The maximum number is `3`.

[Tags ][Tags]

package tju.cs.bigdata;
    
    import java.util.HashSet;
    import java.util.Set;
    
    public class MaxPointsonaLine {
        /**
         * @param points an array of point
         * @return an integer
         * </br>ac
         */
        public int maxPoints(Point[] points) {
            // Write your code here
            int res = 0;
            if(points == null) return res;
     
            // points = delSame(points);
            int len = points.length;
            if(len < 3) return len;
            int samecount = 0;
            for(int i = 0 ; i < len; i++){
                int tmps = 1;
                for(int j = 0; j < len; j++){
                    if(i == j)continue;
                    if(points[i].x == points[j].x && points[i].y == points[j].y){
                        tmps++;
                        continue;
                    }
                    int tmpc = 2;
                    for(int k = 0 ;k < len; k++){
                        if(k == i || k == j){
                            continue;
                        }
                        if(isOnLine(points[i] , points[j] , points[k])){
                            tmpc++;
                        }    
                    }
                    
                    if(tmpc > res)res = tmpc;
                }
                if(tmps > samecount)samecount = tmps;
            }
            
            return Math.max(samecount,res);
        }
    	   /**
         * @param points an array of point
         * @return an integer
         * 思路錯誤
         */
        public int maxPoints1(Point[] points) {
            // Write your code here
            int res = 0;
            if(points == null) return res;
            int len = points.length;
            if(len < 3) return len;
            for(int i = 0 ; i < len-1; i++){
                int tmpc = 2;
                for(int j = 0; j < len; j++){
                    if(j == i || j == i + 1){
                        continue;
                    }
                    if(isOnLine(points[i] , points[i+1] , points[j])){
                        tmpc++;
                    }
                }
                if(tmpc > res)res = tmpc;
            }
            
            return res;
        }
        
        public boolean isOnLine(Point a, Point b, Point c){
            int left = (a.x - b.x)*(c.y - b.y);
            int right = (a.y - b.y)*(c.x - b.x);
            if(left == right){
                return true;
            }else{
                return false;
            }
        }
    	
    	public static void main(String[] args){
    //		String string = "[[0,9],[138,429],[115,359],[115,359],[-30,-102],[230,709],[-150,-686],[-135,-613],[-60,-248],[-161,-481],[207,639],[23,79],[-230,-691],[-115,-341],[92,289],[60,336],[-105,-467],[135,701],[-90,-394],[-184,-551],[150,774]]";
    		String string = "[[0,-12],[5,2],[2,5],[0,-5],[1,5],[2,-2],[5,-4],[3,4],[-2,4],[-1,4],[0,-5],[0,-8],[-2,-1],[0,-11],[0,-9]]";
    		System.out.println(string);
    		String[] stes = string.split("],\\[");
    		int steslen = stes.length; 
    		stes[0] = stes[0].substring(2, stes[0].length());
    		stes[steslen - 1] = stes[steslen - 1].substring(0, stes[steslen - 1].length() - 2);
    		Set<Point> setpoints = new HashSet<>();
    		for(int i = 0 ; i < stes.length; i ++){
    			System.out.println(stes[i] + " ");
    			int x = Integer.parseInt(stes[i].split(",")[0]);
    			int y = Integer.parseInt(stes[i].split(",")[1]);
    			setpoints.add(new Point(x,y));
    		}
    		Point[] points = setpoints.toArray(new Point[setpoints.size()]);
    		System.out.println("最大的：" + new MaxPointsonaLine().maxPoints(points));
    	}
    }

[Tags]: http://www.lintcode.com/en/problem/max-points-on-a-line/#tags