LeetCode 149. Max Points on a Line

题目

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

思路

找共线的最多点数
采用对经过第i个点的直线比较斜率的方式，计算出经过i点的共线最多点
具体的第1个点和第 $2，3，4，...n$个点形成直线的斜率进行比较，如果有相同的那么这些点共线
之后比较第2个点和第 $3，4...n$个点
这是一种时间复杂度为 $O(n^{2})$的实现方法

工程实现

1. 对于斜率为无穷和0的要特殊考虑
2. 对于完全相同的两个点也要单独考虑，这样的两个点可以在计算斜率的时候不考虑，而在经过第i个点的共线最多点时结果要加上该点重复出现的次数
3. 借助unordered_map这一数据结构记录每个斜率出现的次数
4. 在实现的过程中，
   1. 考虑直接用double型记录斜率，但是会出现数值误差漏判错判的情况，比如类似 999999999/999999998和1在比较时误记录为相等的情况
   2. 考虑记录下斜率的分子和分母，新建一个包含两个int的stuct，但是在进行hash时出现尝试引用已删除的函数这样的错误
   3. 最后采用将分子分母记录成字符串的形式来存储在unordered_map中，分子和分母中间用"_“隔开，如果斜率为负则在前面加上”-"，如果斜率为0，记录为"0_1"，斜率为无穷记录为"1_0"，可以比较巧妙地避开很多问题

代码

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        if(points.size() < 2)return points.size(); 
        unordered_map<string, int> m;
        int cmax = 1;
        for(int i = 0; i < points.size(); i ++){
            //cout << i << endl;
            int same = 0;
            int suanzmax = 0;
            for(int j = i + 1; j < points.size(); j ++)
            {
                if(points[j][0] == points[i][0] && points[j][1] == points[i][1]){
                    same ++;
                    continue;
                }
                string nowslope = slope(points[i],points[j]);
                //cout << nowslope << endl;
                m[nowslope] ++;
                suanzmax = max(m[nowslope],suanzmax);
            }
            suanzmax ++;
            suanzmax += same;
            cmax = max(cmax,suanzmax);
            m.clear();
            //cout << endl;
        }
        return cmax;
    }
    string slope(vector<int> point1, vector<int> point2){        
        if(point1[0] == point2[0]){
            return "0_1";
        }
        if(point1[1] == point2[1]){
            return "1_0";
        }
        string res;
        if((point1[1] > point2[1] && point1[0] < point2[0])||(point1[1] < point2[1] && point1[0] > point2[0]))res += "-";
        int mo = abs(point1[1] - point2[1]);
        int de = abs(point1[0] - point2[0]);
        int suanz = maxdivisior(mo,de);
        res += to_string(mo/suanz);
        res += "_";
        res += to_string(de/suanz);
        return res ;
    }
    int maxdivisior(int a, int b){
        if(a == b) return a;
        if(a < b)swap(a,b);
        if(a%b == 0)return b;
        return maxdivisior(b,a%b);
    }
};