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

1.题目

给你一个数组 points ，其中 points[i] = [x_i, y_i] 表示 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

提示：
1 <= points.length <= 300
points[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
points 中的所有点互不相同

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

2.思路

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

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

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