给你一个数组 $points$ ,其中 $points[i] = [x_i, y_i]$ 表示 $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$
$-10^4 <= x_i, y_i <= 10^4$

points 中的所有点 互不相同

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/max-points-on-a-line
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


题解:

class Solution {
public:
    typedef long double ld;

    int maxPoints(vector<vector<int>>& points) {
        int res = 0;
        for(auto& p : points) {
            int ss = 0, vs = 0;  // ss 表示与 p 重合的点, vs 表示穿过 p 且与 x 轴垂直的点(即斜率不存在的点)
            unordered_map<ld, int> cnt;
            for(auto& q : points) {
                if(p == q) ss++;
                else if(p[0] == q[0]) vs++;
                else {
                    ld k = (ld)(p[1]-q[1])/(p[0]-q[0]); // k 为斜率
                    cnt[k]++;
                }
            }
            int c = vs;
            for(auto [k, t] : cnt) c = max(c, t);
            res = max(res, c+ss);
        }
        return res;
    }
};
Last modification:March 18th, 2022 at 01:38 pm
如果觉得我的文章对你有用,请随意赞赏