缀点成线

在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。

请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。

示例 1：
输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true

示例 2：
输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

提示：

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates 中不含重复的点

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

使用向量判断多点是否共线。

求向量

求坐标为$(x_1,y_1)$,$(x_2,y_2)$两点的向量的公式为$\vec{a}=(x_2-x_1,y_2-y_1)$,

如何判断两点是否共线？

• 两个点一定是共线的；
• 判断多点是否共线时，只需要判断两两之间是否可以共线（向量的传递性证明）。

判断两点是否共线的公式
$x_1y_2=x_2y1$

向量共线的传递性证明

证明：
如果$\vec{a}≠0$，那么向量$\vec{b}$与$\vec{a}$共线的充要条件是：存在唯一实数$λ$，使得$\vec{b}=λ\vec{a}$。

若$\vec{a}$与$\vec{b}$共线，$\vec{b}$与$\vec{c}$共线，则$\vec{b}=λ_1 \vec{a}$，$\vec{c}=λ_2\vec{b}$，则$\vec{c}=λ_1 *λ_2 *\vec{a}$.即$\vec{a}$与$\vec{c}$也是共线的。

---

为了高效判断是否两两共线，可以通过中间点判断来减少时间复杂度，即如果存在三个点$p_1,p_2,p_3$，如果$p_1$与$p_2$共线并且$p_2$与$p_3$是共线的，那么$p_1$与$p_3$也是共线的。

因为题目中不包含重复的点，因此通过两两判断向量是否满足 $x_1y_2=x_2y1$，就可以判断所有的点是否共线

class Solution{

    public boolean checkStraightLine(int[][] coordinates) {
        if (coordinates.length <= 2) return true;
        int lastX = coordinates[1][0] - coordinates[0][0];
        int lastY = coordinates[1][1] - coordinates[0][1];

        for (int i = 1; i < coordinates.length; i++) {
            int x = coordinates[i][0] - coordinates[i - 1][0];
            int y = coordinates[i][1] - coordinates[i - 1][1];
            if( lastX * y != x * lastY){
                return false;
            }
        }
        return true;
    }
}

赏

谢谢你请我吃糖果

微信