LeetCode 0149. Maximum number of points on a line

【LetMeFly】149.直线上最多的点数

力扣题目链接：https://leetcode.cn/problems/max-points-on-a-line/

给你一个数组 points ,其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点.求最多有多少个点在同一条直线上.

 

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

 

提示：

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• points 中的所有点 互不相同

方法一：Look at the slope of all other points with this point

The first layer traverses each point.

然后,The second level of traversal traverses each point again,Find the slope between two points,and count with a hash table.

Because they all go through the first point,So points with the same slope are all on a straight line.

Take the maximum number of points with the same slope,It is in the line passing through the first point,The point traversed by the line with the most points.

关于精度问题,C++中使用long double可以通过.

• 时间复杂度$O(n^2)$,其中$n$是点的个数
• 空间复杂度$O(n)$

AC代码

C++

long double ONE = 1;

class Solution {
    
public:
    int maxPoints(vector<vector<int>>& points) {
    
        int ans = 0;
        int n = points.size();
        
        for (int i = 0; i < n; i++) {
    
            unordered_map<long double, int> ma;
            int thisAns = 0;
            for (int j = 0 ; j < n; j++) {
    
                if (i == j)
                    continue;
                long double k = ONE * (points[j][1] - points[i][1]) / (points[j][0] - points[i][0]);
                ma[k]++;
                thisAns = max(thisAns, ma[k]);
            }
            ans = max(ans, thisAns + 1);
        }

        return ans;
    }
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126084170