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

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

程序员文章站 2022-04-01 18:41:16
...

解题思路:

  1. 小于 3 个点的结果就是点数

  2. 点数多于2个点的时候:

    关键:判断每个点和其他点之间的斜率相等的最多的个数
    1)取1个点的坐标,计算出和另一个点斜率的分母和分子
    2) 遍历取1个点 和 1)中的固定一个点用乘数的方式对比斜率是否相等,如果相等,点数 +1;

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */

public class Solution {
    /**
     * 
     * @param points Point类一维数组 
     * @return int整型
     */
    public int maxPoints (Point[] points) {
        if(points.length < 3) return points.length;
        int res = 0;
        for(int i = 1; i < points.length; i++){
            int a = points[i].x;
            int b = points[i].y;
            int xx = a - points[i-1].x;
            int yy = b - points[i-1].y;
            int count = 0;
            if(xx == 0 && yy == 0){
                continue;
            }else{
                for(int j = 0; j < points.length; j++){
                    if((points[j].x - a) * yy == (points[j].y - b) * xx){
                        count++;
                    }
                }
            }
            res = Math.max(res,count);
        }
        return res;
    }
}

上一篇: 高阶函数

下一篇: 判断数据类型