题目描述
在一个 XY 坐标系中有一些点,我们用数组 coordinates
来分别记录它们的坐标,其中 coordinates[i] = [x, y]
表示一个点。
请你来判断,这些点是否在该坐标系中属于同一条直线上。
样例
输入:coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出:true
输入: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
中不含重复的点。
算法
(暴力枚举) $O(n)$
- 通过做差求出前两个点的向量
(x, y)
。 - 从第三个点开始,我们看每个点与第一个点做差后的向量是否和
(x, y)
平行。这里可以通过乘法判断,防止除法出现的精度和整数被 0 除的问题。
时间复杂度
- 仅遍历一遍数组,故时间复杂度为 $O(n)$。
空间复杂度
- 只需要常数的额外空间。
C++ 代码
class Solution {
public:
bool checkStraightLine(vector<vector<int>>& coordinates) {
int n = coordinates.size();
int x = coordinates[1][0] - coordinates[0][0];
int y = coordinates[1][1] - coordinates[0][1];
for (int i = 2; i < n; i++)
if ((coordinates[i][0] - coordinates[0][0]) * y
!= (coordinates[i][1] - coordinates[0][1]) * x)
return false;
return true;
}
};