题目描述

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

示例：

image-20220809110414951

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

提示：

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -10^4 <= xi, yi <= 10^4
  • points 中的所有点 互不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-points-on-a-line
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

枚举所有的点，假设直线经过该点时，该直线所能经过的最多的点数。

假设我们当前枚举到点 i，如果直线同时经过另外两个不同的点 j 和 k，那么可以发现点 i 和点 j 所连直线的斜率恰等于点 i 和点 k 所连直线的斜率。

于是我们可以统计其他所有点与点 i 所连直线的斜率，出现次数最多的斜率即为经过点数最多的直线的斜率，其经过的点数为该斜率现的次数加一（点 i 自身也要被统计）。

IMG_0411(20220809-111214)

关键是这个斜率如何表示？

需要注意的是，浮点数类型可能因为精度不够而无法足够精确地表示每一个斜率，因此我们需要换一种方法来记录斜率。

斜率可以表示为 $$\frac{\bigtriangleup x}{\bigtriangleup y}$$,因此我们可以用分子和分母组成的二元组来代表斜率。我们可以分为以下几种情况：

  • 形如$$\frac{1}{2}和\frac{2}{4}$$这种情况

    虽然这样的二元组不同，但其斜率是相同的。因此我们可以将分子和分母同时除以二者绝对值的最大公约数。

    求最大公约数可以使用欧几里得算法【即辗转相除法】

    1
    2
    3
    private int gcd(int a,int b){
        return b!=0?gcd(b,a%b):a;
    }

    比如：a = 63,b=27;【要保证a是大于b的】

    ① b!=0 –> a = 27,b= 63%27 = 9;

    ②b!=0 –> a = 9,b = 27%9 = 0;

    ③b==0 –> 返回 a=9;

  • 形如$$\frac{-1}{2}和\frac{1}{-2}$$这种情况

    对于这种情况，可以规定。当分母为负数时，分子和分母取反。这样可以保证，分母都是正数，分子是同号的。

    1
    2
    3
    if(y<0){
        x = -x;y=-y;
    }

  • x和y中有一个为0的情况

    此时两数不存在数学意义上的最大公约数，因此我们直接特判这两种情况。当 x==0 时，我们令 y=1；当 y==0时，我们令 x=1 即可。

    1
    2
    3
    4
    5
    if(x==0){
        y=1;
    }else if(y==0){
        x=1;
    }

经过上述操作之后，即可得到最终的二元组(x,y)。

代码如下：

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
class Solution {
    public int maxPoints(int[][] points) {
        int res = 0;
        for (int i = 0; i < points.length; i++) {
            Map<Integer,Integer> map = new HashMap<>();
            /*
            当我们枚举到点 i 时，我们只需要考虑编号大于 i 的点到点 i 的斜率，因为如果直线同时经过编号小于点 i 的点 j，那			 么当我们枚举到 j 时就已经考虑过该直线了；
            */
            for (int j = i+1; j < points.length; j++) {
                // 计算 二元组 x,y
                int x = points[i][0]-points[j][0];
                int y = points[i][1]-points[j][1];
                //分三种情况讨论，二元组
                if(x==0){                  //x==0
                    y=1;
                }else if(y==0){             //y==0
                    x=1;
                }else {                     //x!=0&&y!=0
                    if(y<0){
                        x = -x;y=-y;
                    }
                    int gcd = gcd(Math.abs(x),Math.abs(y)); //求最大公约数
                    x = x/gcd;
                    y = y/gcd;
                }
                int val = x*20001+y;        //计算哈希表的键
                map.put(val,map.getOrDefault(val,0)+1);
            }
            //计算这次循环中，直线最大的点数
            Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
            int num = 0;
            for (Map.Entry<Integer, Integer> entry : entrySet) {
                num = Math.max(num,entry.getValue()+1);//这个entry.getValue()+1表示点 i 自身也要被统计
            }
            
            res = Math.max(res,num);
        }
        return res;
    }
    private int gcd(int a,int b){
        return b!=0?gcd(b,a%b):a;
    }
}

在此基础上，我们还可以做如下优化

  • 在点的总数量小于等于 2 的情况下，我们总可以用一条直线将所有点串联，此时我们直接返回点的总数量即可；

    1
    if(points.length<=2)return points.length;

  • 当我们找到一条直线上的点数经过了图中超过半数的点时，我们即可以确定该直线即为经过最多点的直线；

  • 当我们枚举到点 i（假设编号从 0 开始）时，我们至多只能找到 n - i个点共线。假设此前找到的共线的点的数量的最大值为 k，如果有 k＞= n - i，那么此时我们即可停止枚举，因为不可能再找到更大的答案了。

    1
    if (res >= n - i || res > n / 2) break;

题解代码

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
class Solution {
    public int maxPoints(int[][] points) {
        int res = 0;
        if(points.length<=2)return points.length;
        for (int i = 0; i < points.length; i++) {
            if(res>=points.length-i||res>points.length/2){
                break;
            }
            Map<Integer,Integer> map = new HashMap<>();
            for (int j = i+1; j < points.length; j++) {
                int x = points[i][0]-points[j][0];
                int y = points[i][1]-points[j][1];
                if(x==0){
                    y=1;
                }else if(y==0){
                    x=1;
                }else {
                    if(y<0){
                        x = -x;y=-y;
                    }
                    int gcd = gcd(Math.abs(x),Math.abs(y));
                    x = x/gcd;
                    y = y/gcd;
                }
                int val = x*20001+y;
                System.out.println(val+"  "+x+"  "+y);
                map.put(val,map.getOrDefault(val,0)+1);
            }
            Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
            int num = 0;
            for (Map.Entry<Integer, Integer> entry : entrySet) {
                num = Math.max(num,entry.getValue()+1);
            }
            res = Math.max(res,num);
        }
        return res;
    }
    private int gcd(int a,int b){
        return b!=0?gcd(b,a%b):a;
    }
}

__END__