最佳直线

给定一个二维平面及平面上的 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
通过次数2,058提交次数3,966

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-line-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

向量共线的条件：

x1y2==x2y1

通过两点确定一条直线

A = Y2 - Y1
B = X1 - X2
C = X2Y1 - X1Y2

通过向量共线和一个公共点来判断第三个点是否在直线上

class Solution {
    public int[] bestLine(int[][] points) {
        int[] res = new int[2];
        int num = 0;
        int maxNum = 0;
        int len = points.length;

        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                num = 2;
                if (len - 1 - j + 1 + 1 <= maxNum) break;//已经凑不够了，提前剪枝
                long x1 = points[j][0] - points[i][0];
                long y1 = points[j][1] - points[i][1];

                for (int k = j + 1; k < len; k++) {
                    long x2 = points[k][0] - points[i][0];
                    long y2 = points[k][1] - points[i][1];
                    if (x1 * y2 == x2 * y1) num++;      //满足向量共线的条件
                }
                if (num > maxNum) {
                    maxNum = num;
                    res[0] = i;
                    res[1] = j;
                }
            }
        }
        return res;
    }
}

赏

谢谢你请我吃糖果

微信