链接
https://leetcode-cn.com/problems/check-if-it-is-a-straight-line/
耗时
解题：21 min
题解：11 min
题意
在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。
请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。
思路
观察可以发现：只要所有点坐标 p(xi,yi) 的差值
x
k
1
=
x
i
+
1
−
x
i
xk1=x_{i+1}-x_{i}
xk1=xi+1−xi,
x
k
=
x
i
−
x
i
−
1
xk=x_i-x_{i-1}
xk=xi−xi−1 和
y
k
1
=
y
i
+
1
−
y
i
yk1=y_{i+1}-y_{i}
yk1=yi+1−yi,
y
k
=
y
i
−
y
i
−
1
yk=y_i-y_{i-1}
yk=yi−yi−1 的倍率相同（
x
k
1
x
k
=
=
y
k
1
y
k
⇒
x
k
1
∗
y
k
=
=
y
k
1
∗
x
k
\frac{xk1}{xk} == \frac{yk1}{yk} \Rightarrow xk1*yk == yk1*xk
xkxk1==ykyk1⇒xk1∗yk==yk1∗xk）即在同一条直线上。
时间复杂度：
O
(
n
)
O(n)
O(n)
AC代码
class Solution {
public:
bool checkStraightLine(vector<vector<int>>& coordinates) {
int n = coordinates.size();
if(n <= 2) return true;
int xk = coordinates[1][0] - coordinates[0][0];
int yk = coordinates[1][1] - coordinates[0][1];
for(int i = 2; i < n; ++i) {
int xk1 = coordinates[i][0] - coordinates[i-1][0];
int yk1 = coordinates[i][1] - coordinates[i-1][1];
if((xk1*yk) != (yk1*xk)) {
return false;
}
}
return true;
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
