【LeetCode】3 求最多能有多少个点位于同一直线上

题目:

对于给定的n个位于同一二维平面上的点,求最多能有多少个点位于同一直线上

思路:

1.如果坐标point的数组Point[]为空,或小于三(数组内只有一个坐标或两个坐标),返回数组的长度

2.设最终返回值(有多少点位于同一直线上)为res

3.遍历数组,临时变量count计数,依次取出数组元素也就是point的x坐标,y坐标,求得后一个位置的点坐标与前一个点坐标的差值

4.如果x,y的差值都为0说明为同一点,count++

5.如果不为同一点,如果斜率相等即为同一条直线上,count++

6.嵌套循环,第一轮是第二个元素和第一个元素比,第二轮就是第三个元素和第二个元素比,最后取大者

代码:

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if(points == null || points.length<3)
                return points.length;
            int res =0;
            for(int i=1;i<points.length;i++){
                int count = 0;
                long a = points[i].x;
                long b = points[i].y;
                long dx = a - points[i-1].x;
                long dy = b - points[i-1].y;
                if(dx==0 && dy==0){
                    for(int j=0;j<points.length;j++){
                        if(points[j].x==a && points[j].y==b){
                            count++;
                        }
                    }
                }else{
                    for(int j=0;j<points.length;j++){
                        if((points[j].x-a)*dy==(points[j].y-b)*dx){
                            count++;
                        }
                    }
                }
                res = Math.max(res,count);
            }
            return res;
    }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×