149. 直线上最多的点数-并查集做法

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

博主也是第一次用并查集这个方法，觉得确实很神奇，这个方法应该可以解决很多很难解决的问题，但是使用起来需要我们多做一些应用：

解题代码如下：

int find(int x,int *p){
    while(x!=p[x]){
        x=p[x];
    }
    return x;
}



int maxPoints(int** points, int pointsSize, int* pointsColSize){
    int p[pointsSize];
    int i,j;
    int max=0;
    int cei[pointsSize][2];
    for(i=0;i<pointsSize;i++){
        printf("||");
      
        int  cur=0;
        for(j=i+1;j<pointsSize;j++){
             
            cei[cur][0]=points[i][0]-points[j][0];
             cei[cur][1]=points[i][1]-points[j][1];
            cur++;

        }
  //      printf("cur %d |",cur);
        int hash[pointsSize];
           for(j=0;j<cur;j++){
     
                   p[j]=j;
            }

        

        for(j=0;j<cur;j++){

            hash[j]=0;

            for(int k=j+1;k<cur;k++){
                if(cei[k][0]*cei[j][1]-cei[k][1]*cei[j][0]==0){
                    
                    p[k]=j;

                }
            }
        }
         for(j=0;j<cur;j++){
           
             max=fmax(max,++hash[find(j,p)]);
           //     printf("%d %d |",find(j,p),hash[find(j,p)]);
         }



    }
    printf("max %d ",max);
    return max+1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59