LeetCode 面试题 16.14. 最佳直线

约 7 分钟
文章信息 3 个分类 4 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
数组 哈希表 数学 几何

题目描述

✅ 面试题 16.14. 最佳直线

image-20260929010312049

题意分析

找出经过输入点数最多的直线，返回这条线上最小的两个输入下标。若多条线点数相同，先比较第一个下标，再比较第二个下标；返回的是下标而不是坐标，因此统计共线点时还要保留最早出现的位置。

解法：固定锚点并统计约分方向

核心思路

[!blue]

固定锚点 i 后，一条经过它的非退化直线由方向确定。只扫描 j > i，用坐标差 (dx, dy) 表示从锚点到后续点的方向；除以两分量绝对值的最大公约数，再统一正负号，使 dx > 0，或在竖直时令 dy > 0。这样同一条直线两侧的点得到相同键，水平线与竖直线也无需浮点斜率。

每个方向组保存点数和首次出现的 j。后续下标按升序扫描，因此首次出现的位置就是该方向最小的下标。与锚点重合的点方向为零，不能参与约分；它们位于所有经过锚点的直线上，单独记录 duplicates 和最早的重合点下标。

对每个非零方向，总点数为“锚点 1 个 + 重合点数 + 方向组点数”。该候选的第一个下标是 i，第二个下标取最早重合点与方向组首点的较小者。若没有非零方向，说明后续点都与锚点重合，只需用这一组的总数参与比较。

只扫描后续点不会漏掉最优解：任意一条直线在线上最小下标作为锚点时，都会把其余点完整统计。锚点按升序处理，点数相同的更晚锚点不应覆盖已有答案；同一锚点的方向组由无序哈希表遍历，仍需显式比较第二下标，保证并列结果稳定且最小。

坐标差先转为 64 位再相减。方向用整数约分比较，避免浮点误差，也不需要计算可能超出 64 位范围的叉积。

解题步骤

  1. 从小到大枚举锚点 i，只处理 j>i。
  2. 先用64位相减，再将非零方向约分、统一符号，记录方向人数及最早 j。
  3. 重合点不形成方向，单独记录数量和最早下标。
  4. 每个方向总人数为1+重合数+方向数，第二下标取最早重合点和方向首点的较小者。
  5. 严格更多时更新；同锚点并列时取更小第二下标。若其余点全重合，直接使用该重复点组。

代码实现

class Solution {
    public int[] bestLine(int[][] points) {
        int best = 0;
        int[] answer = {
            0,
            1
        };

        for (int i = 0; i < points.length; i++) {
            Map<String, int[]> groups = new HashMap<>();
            int duplicates = 0;
            int firstDuplicate = points.length;

            for (int j = i + 1; j < points.length; j++) {
                long dx = (long) points[j][0] - points[i][0];
                long dy = (long) points[j][1] - points[i][1];

                if (dx == 0 && dy == 0) {
                    duplicates++;
                    firstDuplicate = Math.min(firstDuplicate, j);
                    continue;
                }

                long g = gcd(Math.abs(dx), Math.abs(dy));

                dx /= g;
                dy /= g;

                if (dx < 0 || (dx == 0 && dy < 0)) {
                    dx = -dx;
                    dy = -dy;
                }

                String key = dx + "," + dy;
                int[] group = groups.get(key);

                if (group == null) {
                    groups.put(key, new int[] {
                        1,
                        j
                    });
                } else {
                    group[0]++;
                }
            }

            if (groups.isEmpty()) {
                if (duplicates + 1 > best) {
                    best = duplicates + 1;
                    answer = new int[] {
                        i,
                        firstDuplicate
                    };
                }
            }

            for (int[] group : groups.values()) {
                int count = 1 + duplicates + group[0];
                int second = Math.min(firstDuplicate, group[1]);

                if (count > best || (count == best && i == answer[0] && second < answer[1])) {
                    best = count;
                    answer = new int[] {
                        i,
                        second
                    };
                }
            }
        }

        return answer;
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long r = a % b;

            a = b;
            b = r;
        }

        return a;
    }
}

func bestLine(points [][]int) []int {
    type direction struct{ dx, dy int64 }
    type group struct{ count, first int }
    gcd := func(a, b int64) int64 {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    abs := func(x int64) int64 {
        if x < 0 {
            return -x
        }
        return x
    }
    best, answer := 0, []int{
        0,
        1,
    }
    for i := range points {
        groups := map[direction]group{}
        duplicates, firstDuplicate := 0, len(points)
        for j := i + 1; j < len(points); j++ {
            dx := int64(points[j][0]) - int64(points[i][0])
            dy := int64(points[j][1]) - int64(points[i][1])
            if dx == 0 && dy == 0 {
                duplicates++
                firstDuplicate = min(firstDuplicate, j)
                continue
            }
            g := gcd(abs(dx), abs(dy))
            dx, dy = dx/g, dy/g
            if dx < 0 || (dx == 0 && dy < 0) {
                dx, dy = -dx, -dy
            }
            key := direction{dx, dy}
            entry, ok := groups[key]
            if !ok {
                entry.first = j
            }
            entry.count++
            groups[key] = entry
        }
        if len(groups) == 0 && duplicates+1 > best {
            best, answer = duplicates+1, []int{
                i,
                firstDuplicate,
            }
        }
        for _, entry := range groups {
            count := 1 + duplicates + entry.count
            second := min(firstDuplicate, entry.first)
            if count > best || (count == best && i == answer[0] && second < answer[1]) {
                best, answer = count, []int{
                    i,
                    second,
                }
            }
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：固定32位坐标下，期望时间 O(n²)。若显式计入欧几里得算法，时间上界 O(n² log U)，U为最大坐标差。
  • 空间复杂度：额外空间 O(n)。

关键点总结

[!green]

任何最优直线都会在其最小下标作为锚点时被完整统计。约分方向避免浮点误差，也避免满范围坐标差的叉积超出64位；竖线和水平线自然归一。

易错点总结

[!yellow]

  • 相减前转换为64位，仅在乘法前转换不足以防止差值溢出。
  • 两个重合点不能单独定义唯一方向，不能把零向量当成与所有点形成同一条直线。
  • 方向要统一正负号，同一直线两侧的点属于同组。
  • 哈希表遍历无序，并列结果必须显式比较第二下标。

相似题目

题目 难度 关联与区别
149. 直线上最多的点数 困难 同样按锚点统计共线方向，本题额外返回最早的两个下标并处理并列。
补充题 154. 最大公约数 简单 用最大公约数把方向向量约成唯一整数键，避免直接用浮点斜率。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/17847778
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！