LeetCode 1232. 缀点成线

约 4 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节
标签
数组 数学 几何

题目描述

✅ 1232. 缀点成线

image-20260929075901744

image-20260929075901900

题意分析

给定平面上若干坐标点，判断它们是否全部落在同一条直线上。题目保证至少有两个点，而且点互不相同，因此前两个点就能确定唯一的一条基准直线。

水平线、竖直线和任意斜线都要处理，输入点也不要求沿某个方向排序。只要任何一点偏离基准直线，答案就是假；仅有两个不同点时必然共线。

解法：向量叉积判共线

核心思路

[!blue]

保存首点 (x0, y0)，用第二点减去首点得到非零方向向量 (dx, dy)。之后每个点也都减去同一个首点，得到偏移向量 (x, y)。当前点在基准线上，当且仅当它的偏移与基准方向平行，反向平行也同样在这条直线上。

两个二维向量平行时，叉积为零，也就是 x * dy - y * dx = 0，等价于 x * dy == y * dx。可以把它看成相同比例的交叉相乘，但不需要实际做除法。

避免除法有两个直接好处：竖直线的横向差为零时仍能正常比较，不会出现除零；整数坐标的交叉乘积可以精确比较，不会因整数除法截断或浮点斜率舍入而混淆不同方向。

基准向量不为零依赖题目的点互异保证。每个后续点都与同一条固定基准线比较，只要全部满足叉积为零，它们便确实都属于这条直线，不需要检查全部点对或重新选择方向。

当前实现用 64 位中间量保存坐标差和乘积，先在宽类型中完成减法，再做交叉相乘。发现任意不相等的乘积就立即返回假，全部通过则返回真。

解题步骤

  1. 保存首点坐标，计算从首点指向第二点的方向 (dx, dy)。
  2. 从第三点开始，计算它相对首点的偏移 (x, y)。
  3. 如果 x * dy != y * dx，立即返回 false。
  4. 所有点检查完成后返回 true。

代码实现

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        long x0 = coordinates[0][0];
        long y0 = coordinates[0][1];
        // 前两个不同点确定固定方向，后续点都相对同一个首点。
        long dx = coordinates[1][0] - x0;
        long dy = coordinates[1][1] - y0;

        for (int i = 2; i < coordinates.length; i++) {
            long x = coordinates[i][0] - x0;
            long y = coordinates[i][1] - y0;

            // 叉积为零才平行，不用除法，竖直线也能直接判断。
            if (x * dy != y * dx) {
                return false;
            }
        }

        return true;
    }
}

func checkStraightLine(coordinates [][]int) bool {
    x0 := int64(coordinates[0][0])
    y0 := int64(coordinates[0][1])
    // 前两个不同点确定固定方向，后续点都相对同一个首点。
    dx := int64(coordinates[1][0]) - x0
    dy := int64(coordinates[1][1]) - y0

    for i := 2; i < len(coordinates); i++ {
        x := int64(coordinates[i][0]) - x0
        y := int64(coordinates[i][1]) - y0
        // 叉积为零才平行，不用除法，竖直线也能直接判断。
        if x*dy != y*dx {
            return false
        }
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n)$，每个点只做固定次数的减法、乘法和比较。
  • 空间复杂度：$O(1)$，仅保存首点、固定方向和当前偏移，无需排序或存储点对。

关键点总结

[!green]

  • 前两个不同点固定基准直线，其他点统一相对同一首点判断。
  • 叉积为零表示方向平行，也允许向量反向，输入顺序不影响结果。
  • 交叉乘法消除斜率除法，统一处理水平、竖直和斜线。

易错点总结

[!yellow]

  • 用整数斜率比较，不同分数斜率可能被截断成相同整数。
  • 直接相除而不处理横向差为零，会在竖直线情况下失败。
  • 交叉配对写错，正确比较的是 x * dy 与 y * dx，而不是同方向分量相乘。
  • 只比较斜率绝对值，会把不同倾斜方向混为一条直线。
  • 先在窄整数中计算差值或乘积、最后才转换类型，无法修复已经发生的中间溢出，应在运算前使用宽类型。

相似题目

题目 难度 关联与区别
149. 直线上最多的点数 困难 共线判定相同，原题在多个候选方向中找最多点，本题只检查全部点是否同线。
812. 最大三角形面积 简单 三点叉积为0等价于三角形面积为0，可用同一表达式判断方向关系。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/62774450
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！