Skip to content

Latest commit

 

History

History
93 lines (77 loc) · 4 KB

149. Max Points on a Line.md

File metadata and controls

93 lines (77 loc) · 4 KB
Raw

149. Max Points on a Line

思路

给定一些二维的点，问共线的点最多有多少个。

思路一

我们知道，一个点P和斜率k确定一条直线。所以我们可以用两层循环，外层循环枚举所有点P，内层循环遍历其他点计算斜率k，同时用hash记录每个k出现了多少次。但这样会存在一个问题那就是斜率k的精度问题，所以我们考虑不将k算成小数而是用最简分数表示k，为了化简分数，我们只需要将分子和分母除以二者最大公倍数即可。

有两个注意点：

  1. 内外层循环的两个点可能重合，此时应该跳过，跳过之前要用一个变量duplicate累积重复的次数，因为最终记录结果时这个点要算多次。

  2. 算斜率时分子分母可能为负号，注意 (-1)/2 和1/(-2)的斜率都是-0.5，所以为了避免这种情况我们统一对其取绝对值，最后将可能存在的负号添加在分母上。

辗转相除法求a和b的最大公约数时间复杂度为log(a+b)，是很快的，不考虑这个时间。如果用的hash而不是treemap那么查询时间复杂度为O(1)，那么总的复杂度就是两层循环，为O(n^2)。

思路二

我们知道，两个（不重合）的点也可以确定一条直线，所以我们可以（用一个两层循环）遍历所有点对，然后再遍历其他点看这三点是否在一条直线上，所以总的是个三层循环。

如何判断三点相等呢，假设三个点分别是(x1,y1), (x2,y2), (x3,y3)；所以第一个点和第二个点可组成向量v1 = (x1-x2, y1-y2) = (dx1, dy1)，所以第一个点和第三个点可组成向量v2=(x1-x3, y1-y3) = (dx2,dy2)，要使三个点共线，那么向量v1和v2应该平行，而且要避免除法，所以有dx1 * dy2 - dy1 * dx2 = 0（这个式子难理解的话可以转换成v1与v2的法向量垂直，两向量垂直的条件是內积为0）。

同样要注意重合点，另外第三层循环是从0开始的！

时间复杂度O(n^3)，亲测确实比思路一慢一些。

C++

思路一

class Solution {
private:
    int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a % b);
    }
    
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        int res = min(2, n);
        for(int i = 0; i < n; i++){
            int duplicate = 1;
            map<pair<int, int>, int>mp;
            for(int j = i+1; j < n; j++){
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1]; // 斜率k = dy/dx
                if(dx == 0 && dy == 0) duplicate++;
                else{
                    int neg = (dx < 0 && dy > 0) || (dx > 0 && dy < 0) ? -1 : 1;
                    dx = abs(dx); dy = abs(dy);
                    int g = gcd(dx, dy);                    
                    mp[{neg * dx / g, dy / g}]++;
                }
            }
            res = max(res, duplicate);
            for(auto it: mp) res = max(res, duplicate + it.second);
        }
        return res;
    }
};

思路二

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        long long dx1, dy1, dx2, dy2;
        int cur, res = min(2, n);
        for(int i = 0; i < n; i++){
            int duplicate = 1;
            for(int j = i + 1; j < n; j++){
                dx1 = points[i][0] - points[j][0];
                dy1 = points[i][1] - points[j][1];
                if(dx1 == 0 && dy1 == 0) duplicate++;
                else{
                    cur = 0;
                    for(int k = 0; k < n; k++){ // 这里从0开始的!!
                        dx2 = points[i][0] - points[k][0];
                        dy2 = points[i][1] - points[k][1];
                        if(dx1*dy2 == dy1*dx2) cur++; 
                    }
                    res = max(res, cur);   
                }
            }
            res = max(res, duplicate);
        }
        return res;
    }
};