leetcode 149. 直线上最多的点数

这是我参与更文挑战的第24天
，活动详情查看更文挑战

题目

给你一个数组 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
 

提示：

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

解题思路

遍历每一个点标i，以点标i为原点向后遍历后面的所有点标，记作j，计算i与j之间的斜率和截距

代码

class Solution {
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    public int maxPoints(int[][] points) {
        int n=points.length,res=1;
        for (int i = 0; i < n; i++) {
            HashMap<String, Integer> map = new HashMap<>();
            int x1=points[i][0],y1=points[i][1];
            int max=0;
            for (int j = i+1; j < n; j++) {
                int x2=points[j][0],y2=points[j][1];
                int a=x1-x2,b=y1-y2;
                int gcd = gcd(a, b);
                String key = (a / gcd) + " " + (b / gcd);
                map.put(key,map.getOrDefault(key,0)+1);
                max=Math.max(max,map.get(key));
            }
            res=Math.max(res,max+1);
        }
        return res;
    }
}
复制代码