题目描述

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

样例

输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

算法分析

固定某个点i

• 1、用哈希表记录经过固定点i的斜率的个数，即 斜率 -> 个数
• 2、枚举其他所有点j，通过gcd算法计算出i点和j点的斜率，用a + "/" + b表示，在哈希表对于的斜率中+1，同时记录与i点重合的点的个数ss，以及i点垂直线上的点的个数vs
• 3、枚举哈希表中的所有斜率，计算出对应个数val + ss的最大值，更新ans

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    static int gcd(int a,int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
    public int maxPoints(int[][] points) {
        int n = points.length;
        int ans = 0;
        for(int i = 0;i < n;i ++)
        {
            HashMap<String, Integer> map = new HashMap<String, Integer>();
            int ss = 0, vs = 0;//ss表示同一个点，vs表示垂直上的点
            for(int j = i;j < n;j ++)
            {
                if(points[i][0] == points[j][0] && points[i][1] == points[j][1])
                {
                    ss ++;
                }
                else if(points[i][0] == points[j][0]) vs ++;
                else
                {
                    int a = points[i][1] - points[j][1];
                    int b = points[i][0] - points[j][0];
                    int c = gcd(a, b);
                    a /= c;
                    b /= c;
                    String t = a + "/" + b;
                    map.put(t, map.getOrDefault(t, 0) + 1);
                }
            }

            int res = vs;
            for(Integer val : map.values())
            {
                res = Math.max(res, val);
            }

            ans = Math.max(ans, res + ss);
        }
        return ans;
    }
}