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

二维坐标中在一条直线上最大点数

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

二维坐标中在一条直线上最大点数

import java.util.HashMap;
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==0)
            return 0;
        if(points.length==1||points.length==2)
            return points.length;
        HashMap<Integer,Integer>map=new HashMap<>();  
        for(int i=0;i!=points.length;i++){

            for(int j=i+1;j!=points.length;j++){

               int k=getXie(points[i],points[j]);
               if(!map.containsKey(k)){
                   map.put(k,1);
               }
               else{
                   int temp=map.get(k);
                   map.put(k,++temp);
               }
            }
        }
        int max=0;
        for(int k:map.keySet()){
             max=Math.max(max,map.get(k));
        }
        return max;
    }
    //获得两个点的斜率
    public int getXie(Point point1,Point point2){
           int a= Math.abs(point2.y-point1.y);
           int b=Math.abs(point2.x-point1.x);
           if(a==0)
             return 0;
           if(b==0)
             return Integer.MAX_VALUE;
          return  a/b;
    }
    //方法二:斜率求解法
    public int maxPoints2(Point[] points) {
        if(points==null||points.length==0)
            return 0;
        if(points.length==1||points.length==2)
            return points.length;
        int max=0;
        for(int i=0;i!=points.length;i++)
        {
            int vcnt=0;  //垂直的点
            int dup=0;   //重复的点
            int curmax=1;
            HashMap<Double,Integer>map=new HashMap<>();
            for(int j=0;j!=points.length;j++){

               if(j!=i){
                  double x1=points[i].x-points[j].x;
                  double y1=points[i].y-points[j].y;
                  if(x1==0&&y1==0)
                  {
                    dup++;   //重复点加1
                  }else if(x1==0)
                  { 
                    if(vcnt==0)
                        vcnt=2;
                    else
                       vcnt++;  //垂直点加1
                    curmax=Math.max(vcnt,curmax);
                  }else{
                   double k=y1/x1;  //斜率
                    if(!map.containsKey(k))
                    {
                         map.put(k,2); 
                    }else{
                         int temp=map.get(k);
                         map.put(k,++temp);    
                    }
                    curmax=Math.max(map.get(k),curmax);
                  }

               }
            }
         max=Math.max(max,curmax+dup);
        }
        return max;

    }
    public static void main(String[]args){
        //System.out.println("Hello World!");
        Point point1=new Point(1,1);
        Point point2=new Point(2,2);
        Point point3=new Point(3,3);
        Point point4=new Point(3,4);
        Point[] points={point1,point2,point3,point4};
        Solution s=new Solution();
        System.out.println(s.maxPoints2(points));

    }
}