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

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

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

题目描述

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

思路:依次遍历所有点,计算两点的斜率(考虑重合点和垂直点的特殊情况),非重合斜率相等的点则位于同一直线上。采用Map存储斜率,其中key值设为Double型的斜率,value值为Integer型的点数。

注意:

Map接口中的常用方法

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

put方法:将指定的键与值对应起来,并添加到集合中。使用put方法时,若指定的键(key)在集合中存在,则返回值为集合中键对应的值(该值为替换前的值),并把指定键所对应的值,替换成指定的新值。若指定的键(key)在集合中不存在,则没有这个键对应的值,返回null,并把指定的键值添加到集合中。

get方法:获取指定键(key)所对应的值(value)。

 

值得注意的是,当斜率计算为0(即两点在一条水平线上)时,要考虑Java double数据类型中的0.0和-0.0问题,HashMap里-0.0和0.0是不同的key。 解决办法: 对获得的double类型数据加上一个0.0。

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
import java.util.*;
public class Solution {
    public int maxPoints(Point[] points) {
        if(points==null)
            return 0;
        if(points.length<3)
            return points.length;
        int i,j;
        double k;
        int res=0;
        for(i=0;i<points.length;i++){
            int same=0;
            int ver=1;
            int num=1;
            Map<Double,Integer> hash=new HashMap<Double,Integer>();
            for(j=i+1;j<points.length;j++){
                if(points[i].x==points[j].x&&points[i].y==points[j].y){
                    same++;
                }
                else if(points[i].x==points[j].x&&points[i].y!=points[j].y){
                    ver++;
                    num=Math.max(num,ver);
                }
                else{
                    double dy=points[j].y-points[i].y;
                    double dx=points[j].x-points[i].x;
                    k=dy/dx+0.0;
                    if(hash.get(k)==null){
                        hash.put(k,2);
                    }
                    else{
                        hash.put(k,hash.get(k)+1);
                    }
                    num=Math.max(num,hash.get(k));
                }
            }
            res=Math.max(res,num+same);
        }
        return res;
    }
}