欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java实现--给定2D平面上的n个点,找出位于同一直线上的最大点数。

程序员文章站 2022-03-02 10:55:06
...

//这是原文。

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

//默认给出的构造函数

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */

理一下思路(穷举):

同一直线上,分两种情况:

1.斜率(Slope)相同

2.有重复的点

public class Solution {
    public int maxPoints(Point[] points) {
        if(points.length == 0){
            return 0;
        }
        if( points.length <= 2 ){
            return points.length;
        }
        
        int max = 2 ;
        for( int i = 0 ; i < points.length ; i++ ){
            int samePosition = 0; //重复位置的点
            int sameSlope = 1;    //斜率相同的点,第一个点
            for( int j = i + 1 ; j < points.length ; j++ ){
                //判断是否为重复位置的点
                int x_distance1 = points[j].x - points[i].x;
                int y_distance1 = points[j].y - points[i].y;
                if( x_distance1 == 0 && y_distance1 == 0 ){
                    samePosition++;
                } else {
                    sameSlope++;//第二个点,所以可以直接++
                    for(int k = j + 1 ; k < points.length ; k++ ){
                        //当判断第3个点的时候可能有人会有疑问为什么不用继续判断是否跟第二个点为相同的点
                        //这是不可行的,因为在判断斜率是否相同的时候又会继续自增一次,会重复加多一次。
                        if ( x_distance1 * y_distance2 == x_distance2 * y_distance1 ) {
                            sameSlope++;
                        }
                    }
                }
                if(max < (samePosition + sameSlope)){
                        max = samePosition + sameSlope;
                }
                sameSlope = 1;
            }
        }
        return max;
    }
}

上一篇: Javascript倒计时

下一篇: Boundary