leetcode149. 直线上最多的点数

暴力

两点确定一条直线，那么只需要判断第三点是否在该直线上即可。枚举每个点，时间复杂度o(n^3)

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n=points.size();
        int ans=1;
        for(int i=0;i<n;i++){
            auto p1=points[i];
            for(int j=i+1;j<n;j++){
                int cnt =2;
                auto p2=points[j];
                for(int k=j+1;k<n;k++){
                   auto p3=points[k];
                   int s1=(p2[1]-p1[1])*(p3[0]-p2[0]);
                   int s2=(p3[1]-p2[1])*(p2[0]-p1[0]);//斜率交叉相乘。
                   if(s1==s2)cnt++;
                }
                ans=max(ans,cnt);
            }
        }
        return ans;
    }
};

哈希优化

class Solution {
public:
    int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
    int maxPoints(vector<vector<int>>& points) {
        int n=points.size();
        if(n<2)return 1;
        int ans=1;
        for(int i=0;i<n;i++){
            unordered_map<string,int>mp;
            int cnt =0;
            for(int j=i+1;j<n;j++){
                int x1 = points[i][0],y1 = points[i][1];
                int x2 = points[j][0],y2 = points[j][1];
                int a = x2-x1,b=y2-y1;
                int k=gcd(a,b);
                string key=to_string(a/k)+" "+to_string(b/k);
                mp[key]++;
                cnt=max(cnt,mp[key]);
            }
             ans=max(ans,cnt+1);
        }
        return ans;
    }
};