题目描述

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

样例

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4
Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

算法1

(hashmap) $O(n^2)$

遍历每一个点，其他各点与之形成的斜率转换为字符串，记录重复频次。同时记录重复点和垂直线上（vertical初始值为1）的点数，得到local max，update global max就是答案

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n=points.size(), res=0;
        if(n==0) return res;
        if(n<3) return points.size();

        for(int i=0;i<n;i++)
        {
            unordered_map<string, int> m;
            int dup=0, vertical=1, local=0;
            for(int j=i+1;j<n;j++)
            {
                auto a=points[i];
                auto b=points[j];
                if(a[0]==b[0] && a[1]==b[1]) dup++;
                else if(a[0]==b[0] ) vertical++;
                else
                {
                    int y=b[1]-a[1], x=b[0]-a[0];
                    int g=__gcd(x,y);
                    string slope=to_string(x/g)+"-"+to_string(y/g);
                    if(m.count(slope))
                        m[slope]++;
                    else
                        m[slope]=2;
                    local=max(local, m[slope]);
                }
            }
            local=max(local+dup, vertical+dup);
            res=max(res, local);
        }
        return res;
    }
};