LeetCode_哈希表_困难_149. 直线上最多的点数

清疚 2023-10-06 23:14 15阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 1：**  
![在这里插入图片描述][ea0d0827f8eb43ab80974bafeef5e7ef.png]  
输入：points = \[\[1,1\],\[2,2\],\[3,3\]\]  
输出：3

**示例 2：**  
![在这里插入图片描述][4d77d03304ce449297dd69da72001d68.png]  
输入：points = \[\[1,1\],\[3,2\],\[5,3\],\[4,1\],\[2,3\],\[1,4\]\]  
输出：4

**提示：**  
1 <= points.length <= 300  
points\[i\].length == 2  
\-104 <= xi, yi <= 104  
points 中的所有点互不相同

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/max-points-on-a-line

## 2.思路 ##

（1）暴力穷举法  
暴力穷举法比较容易想到，由于在平面中两个不同的点可以确定一条直线，所以可以**先穷举两个点的组合（即确定一条直线），然后再检查其余的点是否在该直线上**。

（2）暴力穷举法改进\_哈希表  
思路参考[该用户题解][Link 1]。  
由于两点确定一条直线，所以可以先穷举所有可能出现的直线斜率（即枚举所有的点对），然后使用哈希表统计所有斜率对应的直线上点的数量（即键/值 = 斜率/点的数量），那么所有值中的最大值即为答案。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int maxPoints(int[][] points) {
        
            //最多有 cnt 个点在同一条直线上，由于 1 <= points.length <= 300，所以 cnt 的初始值为 1
            int cnt = 1;
            int n = points.length;
            for (int i = 0; i < n; i++) {
        
                int[] p1 = points[i];
                for (int j = i + 1; j < n; j++) {
        
                    int[] p2 = points[j];
                    //p1 与 p2 一定在一条直线上，故至少有 2 个点在同一条直线上
                    int tmpCnt = 2;
                    for (int k = j + 1; k < n; k++) {
        
                        int[] p3 = points[k];
                        /*
                            (1) 如果 (p1[1] - p2[1])/(p1[0] - p2[0]) == (p2[1] - p3[1])/(p2[0] - p3[0])
                            	那么 p1、p2、p3 这 3 个点在同一条直线上
                            (2) 为了防止整数相除时有精度损失，所以将上面的等式改为：
                            	(p1[0] - p2[0]) * (p2[1] - p3[1]) = (p1[1] - p2[1]) * (p2[0] - p3[0])
                        */
                        if ((p1[0] - p2[0]) * (p2[1] - p3[1]) == (p1[1] - p2[1]) * (p2[0] - p3[0])) {
        
                            tmpCnt++;
                        }
                    }
                    cnt = Math.max(tmpCnt, cnt);
                }
            }
            return cnt;
        }
    }

//思路2————暴力穷举法改进_哈希表
    class Solution {
        
        public int maxPoints(int[][] ps) {
        
            int n = ps.length;
            int cnt = 1;
            for (int i = 0; i < n; i++) {
        
                Map<String, Integer> hashMap = new HashMap<>();
                // 由当前点 i 发出的直线所经过的最多点数量
                int max = 0;
                for (int j = i + 1; j < n; j++) {
        
                    int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
                    int a = x1 - x2, b = y1 - y2;
                    int k = gcd(a, b);
                    String key = (a / k) + "_" + (b / k);
                    hashMap.put(key, hashMap.getOrDefault(key, 0) + 1);
                    max = Math.max(max, hashMap.get(key));
                }
                cnt = Math.max(cnt, max + 1);
            }
            return cnt;
        }
        
        //求 a 和 b 的最大公约数
        public int gcd(int a, int b) {
        
            return b == 0 ? a : gcd(b, a % b);
        }
    }

[ea0d0827f8eb43ab80974bafeef5e7ef.png]: https://img-blog.csdnimg.cn/ea0d0827f8eb43ab80974bafeef5e7ef.png
[4d77d03304ce449297dd69da72001d68.png]: https://img-blog.csdnimg.cn/4d77d03304ce449297dd69da72001d68.png
[Link 1]: https://leetcode.cn/problems/max-points-on-a-line/solution/gong-shui-san-xie-liang-chong-mei-ju-zhi-u44s/