缀点成线
难度:
标签:
题目描述
给定一个数组 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
中不含重复的点
代码结果
运行时间: 18 ms, 内存: 16.5 MB
/*
* The same problem can be solved using Java Streams by leveraging functional operations.
* We start by calculating the initial slope using the first two points and then check all subsequent points using a stream.
* The anyMatch method is used to determine if there exists any point that does not satisfy the collinearity condition.
*/
import java.util.stream.IntStream;
public class SolutionStream {
public boolean checkStraightLine(int[][] coordinates) {
int x1 = coordinates[0][0];
int y1 = coordinates[0][1];
int x2 = coordinates[1][0];
int y2 = coordinates[1][1];
int dx = x2 - x1;
int dy = y2 - y1;
return IntStream.range(2, coordinates.length)
.noneMatch(i -> dy * (coordinates[i][0] - x1) != dx * (coordinates[i][1] - y1));
}
}
解释
方法:
本题解采用了直线斜率的性质来判断多个点是否在同一直线上。首先,计算出第一个点和第二个点之间的斜率作为参考斜率。然后,依次计算后续每个点与其前一个点之间的斜率,并与参考斜率比较。如果所有点与其前一个点的斜率都相等,则这些点共线;否则,不共线。为避免除零错误,当两点水平相同时,斜率被定义为'Inf'(无穷大)。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在处理斜率为无穷大的情况时,你是如何确保所有垂直的点确实都在同一直线上的?是否只是检查x坐标是否相同是否足够?
▷🦆
在计算斜率时,为什么选择使用浮点数除法而不是保持整数形式,比如使用比例的形式(dy, dx)来避免浮点数精度的问题?
▷🦆
如果输入的坐标数组中只有一个点或两个点,该算法是否还适用,如果适用,其输出是否准确?
▷🦆
算法中在比较斜率是否相等时使用了不等式,这是否可能由于浮点精度问题引起错误的判断?该如何改进?
▷