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

我不是女神ヾ 2022-05-23 01:50 143阅读 0赞

![这里写图片描述][70]

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));
    
        }
    }

[70]: /images/20220523/a594c5c7fe964ca7b3b135c5437e2eca.png