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.

Subscribe to see which companies asked this question.

题意

在一个2D平面内有n个点，找到最多数量的点在一条直线上

注意

• 点坐标的范围
• 点坐标的表示，整数？浮点数？浮点数误差？
• 如何判断两点在一条直线上

思路

1.和447.Number of Boomerangs的解法类似，需要选择合适的键值
2.当两个点的斜率相等，表示这两个点在一条直线上。那么就需要统计任意两个点之间的斜率，当某个斜率的出现的频率最大，说明该斜率下连接的直线是最多的。
3.选择斜率作为键，斜率出现的频次为值

E.g:
给定一个点A，需要计算其余点和A点的斜率，会出现三种情况:
(1).和A重合的点
(2).和A具有相同的横坐标，此时斜率无线大
(3).正常的点，计算斜率

代码

int maxPoints(vector<Point> &points) {
    int result = 0;
    for(int i = 0; i < points.size(); i++){
        int samePoint = 1;
        unordered_map<double, int> map;
        for(int j = i + 1; j < points.size(); j++){
            if(points[i].x == points[j].x && points[i].y == points[j].y){
                //重合点也算在一条直线上
                samePoint++;
            }
            else if(points[i].x == points[j].x){
               //斜率无限大的情况
                map[INT_MAX]++;
            }
            else{
                //注意类型
                double slope = double(points[i].y - points[j].y) / double(points[i].x - points[j].x);
                map[slope]++;
            }
        }
        int localMax = 0;
        for(auto it = map.begin(); it != map.end(); it++){
            localMax = max(localMax, it->second);
        }
        //需要加上重合点
        localMax += samePoint;
        result = max(result, localMax);
    }
    return result;
}

结果

代码结果并不能AC，注意这里的键是double类型的，在447.Number of Boomerangs中是为了避免浮点类型为键值。
看测试case，就是一个很大的浮点数，相差甚微，查找表不准确