Easy

题目描述

给你一个坐标数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中的同一条直线上。

示例 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 中不含重复的点

解题思路

解决这道题有两种主要思路：

方法一：斜率法 如果所有点在同一条直线上，那么任意两点之间的斜率都应该相等。但需要注意垂直线的情况（斜率为无穷大），可以通过比较 (y2-y1)/(x2-x1) 是否相等来判断，为避免除法和浮点数精度问题，可以交叉相乘比较 (y2-y1)*(x3-x1) == (y3-y1)*(x2-x1)。

方法二：向量叉积法（推荐） 更优雅的做法是使用向量的叉积。如果三个点 A、B、C 共线，那么向量 AB 和向量 AC 的叉积为 0。对于二维向量，叉积公式为：AB × AC = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)。

具体实现：以前两个点确定一条直线，然后检查后续所有点是否都在这条直线上。只需要验证每个点与前两个点构成的向量叉积是否为 0 即可。

这种方法避免了除法运算，不会有精度问题，代码也更加简洁。

代码实现

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x1 = coordinates[0][0], y1 = coordinates[0][1];
        int x2 = coordinates[1][0], y2 = coordinates[1][1];
        
        for (int i = 2; i < coordinates.size(); i++) {
            int x = coordinates[i][0], y = coordinates[i][1];
            // 使用叉积判断是否共线
            if ((x2 - x1) * (y - y1) != (y2 - y1) * (x - x1)) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x1, y1 = coordinates[0]
        x2, y2 = coordinates[1]
        
        for i in range(2, len(coordinates)):
            x, y = coordinates[i]
            # 使用叉积判断是否共线
            if (x2 - x1) * (y - y1) != (y2 - y1) * (x - x1):
                return False
        return True

public class Solution {
    public bool CheckStraightLine(int[][] coordinates) {
        int x1 = coordinates[0][0], y1 = coordinates[0][1];
        int x2 = coordinates[1][0], y2 = coordinates[1][1];
        
        for (int i = 2; i < coordinates.Length; i++) {
            int x = coordinates[i][0], y = coordinates[i][1];
            // 使用叉积判断是否共线
            if ((x2 - x1) * (y - y1) != (y2 - y1) * (x - x1)) {
                return false;
            }
        }
        return true;
    }
}

var checkStraightLine = function(coordinates) {
    const [x1, y1] = coordinates[0];
    const [x2, y2] = coordinates[1];
    
    for (let i = 2; i < coordinates.length; i++) {
        const [x, y] = coordinates[i];
        // 使用叉积判断是否共线
        if ((x2 - x1) * (y - y1) !== (y2 - y1) * (x - x1)) {
            return false;
        }
    }
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是坐标点的数量，需要遍历除前两个点外的所有点
空间复杂度O(1)，只使用了常数个额外变量