原文链接: https://leetcode-cn.com/problems/best-line-lcci

英文原文

Given a two-dimensional graph with points on it, find a line which passes the most number of points.

Assume all the points that passed by the line are stored in list S sorted by their number. You need to return [S[0], S[1]], that is , two points that have smallest number. If there are more than one line that passes the most number of points, choose the one that has the smallest S[0]. If there are more that one line that has the same S[0], choose the one that has smallest S[1].

Example:

Input:  [[0,0],[1,1],[1,0],[2,0]]
Output:  [0,2]
Explanation:  The numbers of points passed by the line are [0,2,3].

Note:

• 2 <= len(Points) <= 300
• len(Points[i]) = 2

中文题目

给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。

设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。

示例：

输入： [[0,0],[1,1],[1,0],[2,0]]
输出： [0,2]
解释： 所求直线穿过的3个点的编号为[0,2,3]

提示：

• 2 <= len(Points) <= 300
• len(Points[i]) = 2

通过代码

高赞题解

利用向量共线有两大好处：
1.避免开double而进行相对复杂的精度判断
2.不用求直线方程，简化代码量的同时更好理解

大致思路：
首先先确定两个点，再加入第三个点，如果这三个点共线，则num++，不断更新maxn（一条直线穿过点的数量的最大值）
更新时要求解的点也随之更新

class Solution {
public:
    vector<int> bestLine(vector<vector<int>>& points) {
        vector <int>a(2);   //用来存满足条件的两个点
        int num;            //记录直线穿过点的数量
        int maxn=0;         //记录num的最大值
        int n=points.size();
        for (int i=0;i<n-1;i++)
        {
            for (int j=i+1;j<n;j++)
            {
            //先确定两个点
                num=2;
                if (n-1-j+1+1<=maxn)
                break;
                long long x1=points[j][0]-points[i][0];
                long long y1=points[j][1]-points[i][1];
                //记录前两个点的向量（x1,y1）
                for (int k=j+1;k<n;k++)     //不断更新第三个点
                {
                    long long x2=points[k][0]-points[i][0];
                    long long y2=points[k][1]-points[i][1];
                    //第三个点与第一个点构成的向量（x2,y2）
                    if (x1*y2==x2*y1)       //判断两个向量，即三点是否共线
                    num++;
                }
                if (num>maxn)       //更新最优解
                {
                    maxn=num;
                    a[0]=i;
                    a[1]=j;             
                }
            }
        }
        return a;
    }
};

统计信息

通过次数	提交次数	AC比率
3807	6910	55.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言