leetcode
leetcode 1151 ~ 1200
缀点成线

缀点成线

难度:

标签:

题目描述

给定一个数组 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坐标是否相同是否足够?
在处理斜率为无穷大的情况,即两点垂直的情况下,确保所有点在同一直线上的关键是检查这些点的 x 坐标是否完全相同。如果所有具有相同斜率(无穷大)的点的 x 坐标相同,这些点确实都在同一垂直线上。因此,检查 x 坐标的相等性是确保垂直共线性的足够且必要的条件。
🦆
在计算斜率时,为什么选择使用浮点数除法而不是保持整数形式,比如使用比例的形式(dy, dx)来避免浮点数精度的问题?
在计算斜率时使用浮点数除法是为了简化比较过程,使代码更直接和易于理解。然而,这确实引入了浮点数精度的问题。使用整数形式的比例(dy, dx)作为斜率的表示可以避免这类精度问题,同时还可以通过简化比例(例如使用最大公约数)来确保斜率的一致性。这种方法可以更精确地处理斜率比较,尤其是在涉及大量或极端坐标值时更为稳定。
🦆
如果输入的坐标数组中只有一个点或两个点,该算法是否还适用,如果适用,其输出是否准确?
根据常规定义,单个点不能形成线,而两个点总是共线的。因此,如果输入数组中只有一个点,应特别处理这种情况,可能返回一个错误或者特定值。在算法当前实现下,两个点会被正确判断为共线,因为它们之间的斜率是唯一确定的。如果要全面处理,可以在算法开头添加对点数量的检查,以处理不同情况。
🦆
算法中在比较斜率是否相等时使用了不等式,这是否可能由于浮点精度问题引起错误的判断?该如何改进?
由于浮点数的精度问题,直接比较两个浮点数是否相等确实可能引入错误。改进的方法是不直接计算斜率,而是比较两个点间的纵横坐标差的比例。可以通过计算交叉乘积(例如,对于点A和点B的斜率与点B和点C的斜率比较,使用 (y2-y1)*(x3-x2) 是否等于 (y3-y2)*(x2-x1))来避免直接使用浮点数。这种方法只涉及整数运算,避免了浮点数的不精确性。

相关问题